题解 | #矩阵中的路径# 携带标记状态DFS

import java.util.*;


public class Solution {
    boolean dfs(char[][] matrix, int x, int y, int step, String word, int vis[][]) {
        if (step == word.length()) return true;
        
        if (x >= matrix.length || x < 0) return false;
        if (y >= matrix[x].length || y < 0) return false;
if(vis[x][y] == 1) return false;
        if (matrix[x][y] == word.charAt(step)) {
            vis[x][y] = 1;
            boolean result = dfs(matrix, x + 1, y, step + 1, word, vis)
                             || dfs(matrix, x - 1, y, step + 1, word, vis)
                             || dfs(matrix, x, y + 1, step + 1, word, vis)
                             || dfs(matrix, x, y - 1, step + 1, word, vis);
            vis[x][y] = 0;
            return result;
        }
        return false;
    }
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param matrix char字符型二维数组
     * @param word string字符串
     * @return bool布尔型
     */
    public boolean hasPath (char[][] matrix, String word) {
        // write code here
        int row = matrix.length;

        for (int i = 0; i < row; i++) {
            int col = matrix[i].length;
            for (int j = 0; j < col; j++) {
                int vis[][] = new int[100][100];
                if (dfs(matrix, i, j, 0, word, vis)) {
                    return true;
                }
            }
        }
        return false;
    }
}