题解 | JZ12 矩阵中的路径

经典的搜索路径算法。

maze数组的作用是记录走过的路径避免重复走。

搜到ans为true之后就直接返回函数，不再继续往下搜素。

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param matrix char字符型vector<vector<>> 
     * @param word string字符串 
     * @return bool布尔型
     */
    bool ans;
    int dx[4] = {1,0,-1,0};
    int dy[4] = {0,1,0,-1};
    bool maze[20][20];
    bool hasPath(vector<vector<char> >& matrix, string word) {
        // write code here
        ans = false;
        int n = matrix.size();
        if (n == 0) return false;
        int m = matrix[0].size();
        if (m == 0) return false;
//         bool maze[n][m];
        memset(maze, false, sizeof(maze));
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                dfs(i, j, word, 0, n, m, matrix);
            }
        }
        return ans;
    }
    
    void dfs(int x, int y, string word, int pos, int n, int m, vector<vector<char> >& matrix) {
        if (ans) return;
        if (matrix[x][y] == word[pos]) {
            if (pos == word.size()-1) {
                ans = true;
                return;
            }
            maze[x][y] = true;
            for (int i = 0; i < 4; i++) {
                int nx = dx[i] + x;
                int ny = dy[i] + y;
                if (nx < 0 || nx >=n || ny < 0 || ny >= m || maze[nx][ny]) continue;
                dfs(nx, ny, word, pos+1, n, m, matrix);
            }
            maze[x][y] = false;
        }
    }
};