题解 | #矩阵中的路径#

import java.util.*;


public class Solution {
    /**
     * 遍历每个位置当起点试试
     终止条件：到矩阵边界，下一个字符与该位置字符不符合
     返回值：每条查询路径是否有这样的字符串，true，false
     子问题：检查该位置字符与字符串中该字符是否相同，并向它四个相邻方向延申子问题。
     将已经访问过的位置标记为&，避免重复访问。
     * 
     * @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;
        //从每个起点进行递归
        for(int i=0;i<matrix.length;i++){
            for(int j=0;j<matrix[0].length;j++){
               if(isPath(matrix,word,i,j,0))return true;
               
            }
        }
        return false;
    }

    //子函数，传参，字符串遍历的位置，矩阵位置，字符串，矩阵

    public boolean isPath(char[][] matrix,String word,int i,int j,int index){

        //终止条件：成功
        if(index==word.length()){
            return true;
        }
        //到边界
        if(i<0||i>=matrix.length||j<0||j>=matrix[0].length) return false;

        //搜索过该位置也不行
        if(matrix[i][j]=='&') return false;

        if(word.charAt(index)==matrix[i][j]){
            //搜索附近四个方向查看是否匹配
            char tmp = matrix[i][j];
            matrix[i][j] ='&';
            boolean res = isPath(matrix,word,i-1,j,index+1)||
            isPath(matrix,word,i+1,j,index+1)||
            isPath(matrix,word,i,j-1,index+1)||
            isPath(matrix,word,i,j+1,index+1);
            //回溯,结束之后
            matrix[i][j] = tmp;
            //返回结果
            return res;
        }

        return false;
    }
}