剑指 Offer 12. 矩阵中的路径

题目链接：https://leetcode-cn.com/problems/ju-zhen-zhong-de-lu-jing-lcof/

class Solution {
public:
    // vector<vector<bool>> vis;
    // bool vis[205][205];

    bool dfs(vector<vector<char>>& board, int x, int y, int cur, string str) {

        if (x < 0 || x >= board.size()) {
            return false;
        } 
        if (y < 0 || y >= board[0].size()) {
            return false;
        }
        
        if (board[x][y] == str[cur] && cur == str.size()-1) {
            return true;
        }

        if(board[x][y] == str[cur]) {
            // return true;
            board[x][y] = '\0';
            bool res = dfs(board, x+1, y, cur+1, str) || dfs(board, x-1, y, cur+1, str) || dfs(board, x, y+1, cur+1, str) || dfs(board, x, y-1, cur+1, str);
            board[x][y] = str[cur];
            return res;
        } else {
            return false;
        }
    }

    bool exist(vector<vector<char>>& board, string word) {
        // return dfs()
        for (int i = 0; i < board.size(); i++) {
            for (int j = 0; j < board[0].size(); j++) {
                if (dfs(board, i, j, 0, word) == true) {
                    return true;
                }
            }
        }
        return false;
    }
};