题解 | #矩阵中的路径#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param matrix char字符型二维数组 
     * @param word string字符串 
     * @return bool布尔型
     */
    public boolean hasPath (char[][] matrix, String word) {
        char[] arr = word.toCharArray() ;
        //标记
        boolean[][] isvisit = new boolean[matrix.length][matrix[0].length] ;
        //从每一个点出发去找
        for(int i = 0 ; i < matrix.length ; i ++) {
            for(int j = 0 ; j < matrix[0].length ; j ++) {
                //只有起点相同才有找下去的必要
                if(matrix[i][j] == word.charAt(0)) {
                    //找到立即返回
                    if(dfs(matrix,i,j,arr,0,isvisit)) {
                        return true ;
                    }
                }
            }
        }
        return false ;
    }
    
    /*
    从map[i][j]出发 能不能找到 word[index]及其以后的字符序列
    */
    public boolean dfs(char[][] map , int i , int j , char[] word , int index,boolean isVisit[][]) {
        if(index == word.length) {
            return true ;
        }
        if(i < 0 || i >= map.length || j < 0 || j >= map[0].length) {
            return false ;
        }
        //若已经找过 直接返回false
        if(isVisit[i][j]) {
            return false ;
        }
        if(map[i][j] != word[index]) {
            return false ;
        } else {
            //标记
            isVisit[i][j] = true ;
            //以当前点的四周每个点为起点再去找
            boolean flag = dfs(map,i-1,j,word,index+1,isVisit)||
                           dfs(map,i+1,j,word,index+1,isVisit)||
                           dfs(map,i,j-1,word,index+1,isVisit)||
                           dfs(map,i,j+1,word,index+1,isVisit) ;
            //解除标记
            isVisit[i][j] = false ;
            return flag ;
        }
        
        
    }
}