题解 | #矩阵中的路径#

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param matrix char字符型二维数组 
     * @param word string字符串 
     * @return bool布尔型
     */
    public boolean hasPath (char[][] matrix, String word) {
        // write code here
        if(matrix == null || word == null) {
            return false;
        }
        int row = matrix.length;
        int col = matrix[0].length;
        boolean[][] visit = new boolean[row][col];
        for(int i=0; i < row; i++) {
            for(int j=0; j < col; j++) {
                if(dfs(matrix, word, i, j, visit, 0)) {
                    return true;
                }
            }
        }
        return false;
    }
    
    // (i,j)为当前访问的坐标地址, visit存储访问过的路径， cur表示当前匹配s的下标
    boolean dfs(char[][] m, String s, int i, int j, boolean[][] visit, int cur) {
        if(i < 0 || j < 0 || i >= m.length || j >= m[0].length || m[i][j] != s.charAt(cur)) {
            return false;
        }
        if(visit[i][j]) {
            return false;
        }
        if(cur == s.length() - 1) {
            return true;
        }
        visit[i][j] = true;
        cur++;
        if(dfs(m,s,i-1,j,visit,cur) || dfs(m,s,i+1,j,visit,cur) ||
          dfs(m,s,i,j-1,visit,cur) || dfs(m,s,i,j+1,visit,cur)) {
            return true;
        }
        visit[i][j] = false;
        return false;
    }
}