题解 | #矩阵中的路径#

感染算法的思想：同样类型的题还有求岛屿数量，和这个题的思想是一样的。

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param matrix char字符型二维数组 
     * @param word string字符串 
     * @return bool布尔型
     */
    public boolean hasPath (char[][] matrix, String word) {
        // write code here
        
        char[] chars = word.toCharArray();
        for(int i = 0 ; i< matrix.length;i++){
            for(int j = 0; j< matrix[0].length;j++){
                if(dfs(matrix,chars,i,j,0)){
                    return true;
                }
            }
        }
        return false;
    }
    
    public boolean dfs(char[][] matrix,char[] word,int i,int j,int index){
        if(i< 0 || i >= matrix.length || j<0|| j>= matrix[0].length || matrix[i][j] != word[index]){
            return false;
        }
        if(index == word.length-1){
            return true;
        }
        index++;
        char tmp = matrix[i][j];
        matrix[i][j] = '.';//修改后还要复原，否则会影响之后的找起点
        boolean res = dfs(matrix,word,i+1,j,index) || 
             dfs(matrix,word,i-1,j,index) || 
             dfs(matrix,word,i,j+1,index) || 
            dfs(matrix,word,i,j-1,index);
        matrix[i][j] = tmp;
        return res;
    }
}