1.题目

https://leetcode-cn.com/problems/word-search/

2.思路

（1）可以复习【1091】三维&二维BFS&复习这篇，在这篇的方向移动处理是设置2个数组（x轴、y轴），也可以换成2维vector数组，也可以vector<pair<int,int>>即对于每个pair对的元素引用是first，second。
【LeetCode5665】从相邻元素对还原数组、【LeetCode39】组合总和（回溯法）。

（2）只要有一处返回true，就能说明二维数组中能找到对应的单词；

（3）二维visited数组和board数组大小相同（在exist函数里就要设置好大小了，否则后面会报错-空指针啥的，所以要将visited二维数组作为参数传引用），visited数组用于表示每个位置是否被访问过——dfs遍历相邻位置时跳过已经访问过的位置。

3.代码

class Solution {
private:
    vector<pair<int, int>> directions{{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
    //vector<vector<int>>visited;
public:
    bool dfs(vector<vector<char>>& board,vector<vector<int>>&visited,int i, int j, string& word, int k) {
        if (board[i][j]!= word[k]){
            return false;//当前字符不匹配
        }
        if (k==word.length()-1) {
            return true;//当前已经访问到末尾，即完成word匹配
        }
        visited[i][j]=true;//标记访问过
        bool result = false;
        //for (const auto& dir: directions) {
        for(auto dir:directions){
            int x=i+dir.first,y=j+dir.second;
            if (x>= 0 && x< board.size() && y>= 0 && y< board[0].size()) {//若没越界
                if (!visited[x][y]) {//不和上面写在一起是为了可读性
                    bool flag=dfs(board,visited,x,y,word,k+1);
                    if(flag){   
                        result=true;
                        break;
                    }
                }
            }
        }
        visited[i][j]=false;//恢复原状
        return result;
    }

    bool exist(vector<vector<char>>& board, string word) {
        int high= board.size();
        int width= board[0].size();
        vector<vector<int>> visited(high, vector<int>(width));
        for (int i=0;i<high;i++) {
            for (int j=0;j<width;j++) {//分别从每个单词开始dfs
                bool flag=dfs(board,visited,i,j,word,0);
                if(flag){
                    return true;
                }
            }
        }
        return false;
    }
};

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
  
43
  
44
  
45
  
46
 

4.reference

（1）https://wzhfy.blog.csdn.net/article/details/113363432
（2）单词搜索

文章来源: andyguo.blog.csdn.net，作者：山顶夕景，版权归原作者所有，如需转载，请联系作者。

原文链接：andyguo.blog.csdn.net/article/details/113785977