JAVA题解 | #矩阵中的路径#

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param matrix char字符型二维数组 
 * @param word string字符串 
 * @return bool布尔型
 */

 
public class Solution {
import java.util.*;
public boolean hasPath (char[][] matrix, String word) {
    int len = word.length();
    char start = word.charAt(0);
    int m=0;int n=0;
    boolean[][] lu = 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(start==matrix[i][j])//先找到第一个字符的位置
        {m=i;n=j;lu[m][n]=true;
         if(dfs(matrix,word,m,n,lu,start,0,0)==true) return true;
         lu[m][n]=false;//可能有多个与首字符相同的字符，所以要将走过的记录还原
         }
        
    }
return false;
}
    private boolean dfs(char[][] matrix,String word,int m, int n,boolean[][] lu,char read,int x,int go){
        
            if(matrix[m][n]==word.charAt(x)&&x==word.length()-1){return true;}
            read = word.charAt(++x);
        boolean re=false;
        for(go=0;go<4;go++){//记录四个方向，我这里加了方向输出，可以观察到走位
            if(m<matrix.length-1&&lu[m+1][n]!=true&&matrix[m+1][n]==read&&go==0)
            {lu[m+1][n]=true;m=m+1;System.out.print("下"); re=dfs(matrix,word,m,n,lu,read,x,go);lu[m][n]=false;m=m-1;}
            if(n<matrix[0].length-1&&lu[m][n+1]!=true&&matrix[m][n+1]==read&&go==1)
            {lu[m][n+1]=true;n=n+1;System.out.print("右"); re=dfs(matrix,word,m,n,lu,read,x,go);lu[m][n]=false;n=n-1;}
            if(m>0&&lu[m-1][n]!=true&&matrix[m-1][n]==read&&go==2)
            {lu[m-1][n]=true;m=m-1;System.out.print("上"); re=dfs(matrix,word,m,n,lu,read,x,go);lu[m][n]=false;m=m+1;}
            if(n>0&&lu[m][n-1]!=true&&matrix[m][n-1]==read&&go==3)
            {lu[m][n-1]=true;n=n-1;System.out.print("左"); re=dfs(matrix,word,m,n,lu,read,x,go);lu[m][n]=false;n=n+1;}
            
            if(re==true) return true;
            

    }
        return false;

    }
}