[数据结构与算法]LeetCode79-单词搜索-递归-深搜-矩阵

原题链接

Note ：

爆搜，解释写到代码里面了

代码如下：

class Solution {
public:
    bool exist(vector<vector<char>>& board, string word) {
        int n = board.size();
        if(!n)  return false;
        int m = board[0].size();

        for(int i = 0; i < n; i ++)
            for(int j = 0; j < m; j ++)
                if(dfs(board, word, i, j, 0))   return true;
        
        return false;
    }

    //当前下标，u是判断到word的第几个位置了
    bool dfs(vector<vector<char>>& board, string& word, int x, int y, int u){
        //不匹配了，false,找下一个位置
        if(board[x][y] != word[u])  return false;
        //这一位匹配上了，并且已经是字符串的最后一位了
        if(u == word.size() - 1)    return true;
        int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};
        //把刚才走过的写成"."避免重复走相同的格子（就是不让他走回头路）
        char t = board[x][y];
        board[x][y] = '.';
        for(int i = 0; i < 4; i ++){
            int a = x + dx[i], b = y + dy[i];
            if(a < 0 || a >= board.size() || b < 0 || b >= board[0].size() || board[a][b] == '.')    continue;
            if(dfs(board, word, a, b, u + 1))   return true;
        }
        board[x][y] = t;
        return false;
    }
};