思路:

简单搜索

总结:

1. 第一次做的时候忘记加 visited 数组了

2. 做完 kedebug 的搜索题, 简单搜索问题都变得像小绵羊一样温顺了

3. 还是 dfs 框架. 书上所写的 dfs 框架, 一般由 DFS, dfs 两个函数拼成, DFS 负责接收参数和变量初始化, dfs 负责一般情况下的遍历. 两个函数连用比仅用一个 dfs 要好的多, 因为减少了很多判断语句. 下面的代码, 相当于 DFS+ dfs.

 

代码:

#include 
     
      #include 
      
       #include 
       
        using namespace std;const int MAXN = 200;bool visited[MAXN][MAXN];int dire[4][2] = {-1,0, 1,0, 0,-1, 0,1};class Solution {public:	vector
        
         
           > vec;	string str;	bool ans;	void dfs(const int &i, const int &j, const int &depth) {		if(depth == str.size()) {			ans = true;			return;		}		for(int d = 0; d < 4 && !ans; d ++) {// directions			int newi = i+dire[d][0], newj = j+dire[d][1];			if(newi >= 0 && newi 
          
           = 0 && newj < vec[newi].size() && !visited[newi][newj]) { if(vec[newi][newj] == str[depth]) { visited[newi][newj] = 1; dfs(newi, newj, depth+1); visited[newi][newj] = 0; } } } } bool exist(vector
           
            
              > &board, string word) { vec = board; str = word; ans = false; memset(visited, 0, sizeof(visited)); for(int i = 0; i < board.size()&&!ans; i ++) { for(int j = 0; j < board[i].size()&&!ans; j++) { if(board[i][j] == word[0]) { visited[i][j] = true; dfs(i, j, 1); visited[i][j] = false; } } } return ans; }};