剑指 Offer 12. 矩阵中的路径

题目链接：剑指 Offer 12. 矩阵中的路径

方法：DFS

解题思路

根据 \(word\) 中的第一个字母，从 \(board\) 网格中开始查找，通过 \(DFS\) 算法思想实现。
注意：

• 在每一轮开始查找前，每个位置的标记应该清除；
• 每一个位置有上 下 左 右四个方向可以选择；
• \(DFS\) 查找进入下一步时要将位置标记上，回溯后，要将该位置标记清除；
• 其中 \(DFS\) 的终止条件：
  • \(DFS\) 查找的 \(depth\) (深度起始为0) == \(word.size() - 1\);
  • 上下左右四个方向都走不通时。

代码

class Solution {
private:
    bool IsVisit[6][6];
    bool flag;
    int m, n;

public:
    Solution(){
        memset(IsVisit, 0, sizeof(IsVisit));
        flag = false;
    }

    void dfs(int x, int y, int depth, vector<vector<char>>& board, string word){
        if (depth == word.size() - 1) {
            flag = true;
            return ;
        }

        if (x - 1 >= 0 && board[x - 1][y] == word[depth + 1] && !IsVisit[x - 1][y]) {
            IsVisit[x - 1][y] = true;
            dfs(x - 1, y, depth + 1, board, word);
            IsVisit[x - 1][y] = false;
        }
        if (x + 1 < m && board[x + 1][y] == word[depth + 1] && !IsVisit[x + 1][y]) {
            IsVisit[x + 1][y] = true;
            dfs(x + 1, y, depth + 1, board, word);
            IsVisit[x + 1][y] = false;
        }
        if (y - 1 >= 0 && board[x][y - 1] == word[depth + 1] && !IsVisit[x][y - 1]) {
            IsVisit[x][y - 1] = true;
            dfs(x, y - 1, depth + 1, board, word);
            IsVisit[x][y - 1] = false;
        }
        if (y + 1 < n && board[x][y + 1] == word[depth + 1] && !IsVisit[x][y + 1]) {
            IsVisit[x][y + 1] = true;
            dfs(x, y + 1, depth + 1, board, word);
            IsVisit[x][y + 1] = false;
        }

        return ;
    }

    bool exist(vector<vector<char>>& board, string word) {
        m = board.size();
        n = board[0].size();
        char start = word.front();
        int depth = 0;

        for (int i = 0; i < m; i ++ ) {
            for (int j = 0; j < n; j ++ ) {
                if (board[i][j] == start){
                    IsVisit[i][j] = true;
                    dfs(i, j, depth, board, word);
                    if (flag == true) break;
                    memset(IsVisit, 0, sizeof(IsVisit));
                }
            }
            if (flag == true) break;
        }

        return flag;
    }
};