题目：

 

 

解答：

回溯法。

（1）在board中找到一个位置，使得board[i][j] == word[0]，可以作为搜索的入口；

（2）由于一个格子不能重复进入，因此需要定义一个visit数组，保证每个格子只进入一次；

（3）找到一个可行解即返回true。若该次搜索返回false，那么进行步骤1.，找到下一个可行的入口，进入下一次搜索；

（4）直到遍历完整个board，仍没有搜索到目标路径，返回false；

 1 class Solution {
 2 public:
 3 
 4     vector<vector<int>> dxy = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
 5     int rows, cols;
 6     bool dfs(vector<vector<char>>& board, vector<bool>& visit, int i, int j, string& word, int idx)
 7     {
 8         if(board[i][j] != word[idx]) 
 9         {
10             return false;
11         }
12         visit[i*cols+j] = true;
13         idx++;
14         for(auto xy : dxy)
15         {
16             int x = xy[0] + i;
17             int y = xy[1] + j;
18             if(x < 0 || x >= rows || y < 0 || y >= cols || visit[x*cols+y]) 
19             {
20                 continue;
21             }
22             else
23             {
24                 if(dfs(board, visit, x, y, word, idx)) 
25                 {
26                     return true;
27                 }
28             }
29         }
30         visit[i*cols+j] = false;
31         if(idx == word.size()) 
32         {
33             return  true;
34         }
35         return false;
36     }
37 
38     bool exist(vector<vector<char>>& board, string word) 
39     {
40         if(word == "")  
41         {
42             return false;
43         }
44         rows = board.size();
45         cols = board[0].size();
46         vector<bool> visit(rows * cols, false);
47         for(int i = 0;i < rows; i++)
48         {
49             for(int j = 0; j < cols; j++)
50             {
51                 if(board[i][j] == word[0])
52                 {
53                     if(dfs(board, visit, i, j, word, 0)) 
54                     {
55                         return true;
56                     }
57                 }
58             }
59         }
60         return false;
61     }
62 };