题解 | #矩阵中的路径 #

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param matrix char字符型二维数组 
     * @param word string字符串 
     * @return bool布尔型
     */
    public boolean hasPath (char[][] matrix, String word) {
        // write code here
        if(matrix.length == 0 && matrix[0].length == 0){
            return false;
        }
        //判断matrix中的所有点按照深度优先遍历能否走通
        char [] words = word.toCharArray();
            for(int row = 0; row < matrix.length; row++){
                for(int col = 0; col < matrix[0].length; col++){
                    if(dfs(matrix, row, col, 0, words)){
                        return true;
                }
            }
        }
        return false;
    }

    public static boolean dfs(char[][] matrix, int row, int col, int index, char[] words){
        //越界或不相等，return false
        if(row < 0 || row >= matrix.length || col < 0 || col >= matrix[0].length || matrix[row][col] != words[index]){
            return false;
        }
        //比对完成，return true
        if(index == words.length - 1){
            return true;
        }
        //经过过的位置改为‘#’,应对示例二
        char tmp = matrix[row][col];
        matrix[row][col] = '#';
        //看向四个方向是否有可行解
        boolean res =
                   dfs(matrix, row - 1, col, index + 1, words)
                || dfs(matrix, row, col - 1, index + 1, words)
                || dfs(matrix, row + 1, col, index + 1, words)
                || dfs(matrix, row, col + 1, index + 1, words);
        //矩阵复原
        matrix[row][col] = tmp;
        return res;
    }
}