矩阵中的路径

问题：矩阵中的路径剑指 Offer 12. 矩阵中的路径 - 力扣（LeetCode）

思路：DFS+剪枝；

首先可以从矩阵中的任何一点出发进行搜索；时间复杂度O(MN)；

从某个board[ i ][ j ]出发，判断它的四个方向；下 、上、右、 左，走过的点标记为 ' \0 ' ，用来防止重复访问；因此至多只有三个方向可以走，但是通写成四个dfs，用 || 连接；

board[ i ][ j ] == word[ k] 就继续寻找下一个点；

直到 k == word.size() -1;完全匹配时 进行回溯，并将标记的点还原为原来的值；

 时间复杂度：O(MN 3^k); 空间复杂度：O(K).

class Solution {
public:
    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(dfs(board,word,i,j,0)) return true;//从一个点开始dfs；匹配失败就进行下一次dfs
            }
        }
        return false;
    }
private:
    int row,col;
    bool dfs(vector<vector<char>>& b, string w, int x,int y,int k){
        if(y >= col || y <0 || x < 0 || x >= row || b[x][y] != w[k]) return false;
        if(k == w.size() -1) return true;
        b[x][y] = '\0';
        bool res = dfs(b,w,x+1,y,k+1)||dfs(b,w,x-1,y,k+1)||
                    dfs(b,w,x,y+1,k+1)||dfs(b,w,x,y-1,k+1);
        b[x][y] = w[k];
        return res;
    }
};