剑指 Offer 12. 矩阵中的路径（中等）

孜孜不倦fly / 2023-08-11 / 原文

题目：

class Solution {
public:
    int row, col;
    bool traversal(vector<vector<char>>& board, string word, int i, int j, int k){        //传入棋盘，字符串，当前棋盘元素坐标，字符串索引
        if(i<0||i>=row||j<0||j>=col||board[i][j]!=word[k]) return false;                  //越界或者元素不相等，返回false
        if(k==word.size()-1) return true;                                                 //字符串索引到达终点，说明全部匹配
        board[i][j]='\0';                         //修改为空字符来标记，防止之后重复搜索。比如第一个A匹配了，下一个是B，B按照下、上、右、左的顺序递归，此时向左递归的话会重复访问A，但因为A为'\0'了，所以会返回false
        bool res = traversal(board, word, i+1, j, k+1)||traversal(board, word, i-1, j, k+1)  //按照下、上、右、左的顺序递归
        ||traversal(board, word, i, j+1, k+1)||traversal(board, word, i, j-1, k+1);
        board[i][j] = word[k];      //恢复棋盘，以免影响exist中的遍历
        return res;
    }
    bool exist(vector<vector<char>>& board, string word) {
        row = board.size();
        col = board[0].size();
        for(int i = 0; i < row; i++){
            for(int j = 0; j < col; j++){
                if(traversal(board, word, i, j, 0)) return true;
            }
        }
        return false;
    }
};

以上方法转自：
作者：Krahets
链接：https://leetcode.cn/problems/ju-zhen-zhong-de-lu-jing-lcof/solutions/103929/mian-shi-ti-12-ju-zhen-zhong-de-lu-jing-shen-du-yo/
来源：力扣（LeetCode）