leetcode热题100（79. 单词搜索）dfs回溯 c++

链接：79. 单词搜索 - 力扣（LeetCode）

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

示例 1：

输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
输出：true

示例 2：

输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
输出：true

示例 3：

输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
输出：false

提示：

• m == board.length
• n = board[i].length
• 1 <= m, n <= 6
• 1 <= word.length <= 15
• board 和 word 仅由大小写英文字母组成

进阶：你可以使用搜索剪枝的技术来优化解决方案，使其在 board 更大的情况下可以更快解决问题？、

思路

        对每一个board的位置为初始位置开始枚举，dfs记录一下当前枚举到哪个元素，要是枚举到最后一个元素即可找到解，否则返回false了，

        唯一注意的就是遍历过的位置要把它标记一下避免重复判断，我们可以先让他等于“/0”后面回溯把它变回来即可

代码如下

class Solution {
public:
    int n,m;
    int len;
    int dx[4]={-1,0,1,0};
    int dy[4]={0,-1,0,1};
    bool exist(vector<vector<char>>& board, string word) {
        n = board.size();
        m = board[0].size();
        len = word.size();
        for(int i=0;i<n;i++)
            for(int j=0;j<m;j++)
            {
                if(dfs(i,j,0,board,word)) return true;
            }
        return false;
    }

    bool dfs(int x,int y,int k,vector<vector<char>>& board, string word){
        
        if(x<0||x>=n||y<0||y>=m||word[k]!=board[x][y]) return false;
        //cout<<x<<" "<<y<<" "<<k<<endl;
        board[x][y]='/0'; // 已经遍历过的标记一下，下次不能重复遍历
        if(k==len-1) return true;  //已经找到满足word的字符串返回
        bool flag = false;
        for(int i=0;i<4;i++){
            int a = x+dx[i];
            int b = y+dy[i];
            flag|=dfs(a,b,k+1,board,word);
        }
        board[x][y]=word[k];  //复原，下一次重新遍历
        return flag;
    }
};