剑指 Offer 12. 矩阵中的路径

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

 

solution:

        dfs

class Solution {
public:
    int dx[4] = {-1, 0, 1, 0};
    int dy[4] = {0, 1, 0, -1};
    vector<vector<bool>> vis;   //保存是否遍历过该点 
    bool exist(vector<vector<char>>& board, string word) {
        vis = vector<vector<bool>> (board.size(), vector<bool> (board[0].size(), false));
        for(int i = 0;i < board.size();i++)
            for(int j = 0;j < board[0].size();j++) {
                if(dfs(board, word, 0, i, j)) return true;
            }
        return false;
    }

    bool dfs(vector<vector<char>>& board, string &word, int u,int x,int y) {
        if(board[x][y] != word[u]) return false;
        if(u == word.size() - 1) return true;

        vis[x][y] = true;
        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() || vis[a][b]) continue;
            if(dfs(board, word, u + 1, a, b)) return true;
        }
        vis[x][y] = false;
        return false;
    }
};