题解 | #矩阵中的路径#

import java.util.*;
public class Solution {
   
    public boolean flag=false;
    public boolean visited[][];
  // public  ArrayList<Character> arr=new ArrayList<Character>();
    StringBuilder sb=new StringBuilder();boolean next=false;
    public boolean hasPath (char[][] matrix, String word) {
        // write code here
    
        if(matrix.length==0) return false;
        visited=new boolean[matrix.length][matrix[0].length];
       
      for(int i=matrix.length-1;i>=0;i--)
      {
          if(flag==true) return true;
          for(int j=matrix[i].length-1;j>=0;j--)
        {

              dfs(matrix,i,j,word);
              if(flag==true) return true;
         }
      }
        return false;
        
    }
    void dfs(char[][] matrix,int x,int y,String word)
    {
        if(flag==true) return;
        visited[x][y]=true;
    //    arr.add(matrix[x][y]);
        
        sb.append(matrix[x][y]);
      next =  sb.charAt(sb.length()-1)!=word.charAt(sb.length()-1) ? true: false;
         
           
           
       
      //  if(tostring(a).equals(word))
        String cmp=new String(sb);
        if(cmp.equals(word))
        {
            flag=true;
            return;
        }
        //left
       if(y-1>=0 && visited[x][y-1]!=true && flag!=true && next!=true) 
       {
           dfs(matrix,x,y-1, word);
       }
        //down
         next =  sb.charAt(sb.length()-1)!=word.charAt(sb.length()-1) ? true: false;
         if(x+1<=matrix.length-1 && visited[x+1][y]!=true && flag!=true &&  next!=true)//left
       {
           dfs(matrix,x+1,y, word);
       }
        //right
         next =  sb.charAt(sb.length()-1)!=word.charAt(sb.length()-1) ? true: false;
         if(y+1<=matrix[0].length-1 && visited[x][y+1]!=true && flag!=true && next!=true)
       {
           dfs(matrix,x,y+1,word);
       }
        //up
         next =  sb.charAt(sb.length()-1)!=word.charAt(sb.length()-1) ? true: false;
         if(x-1>=0 && visited[x-1][y]!=true && flag!=true && next!=true)
       {
           dfs(matrix,x-1,y,word);
       }
      //  if(arr.size()>0)
     //   arr.remove(arr.size()-1);
        if(flag!=true)
        sb.deleteCharAt(sb.length()-1);
        visited[x][y]=false;
    }
    
  /*  String tostring(ArrayList<Character> arr)
    {
        char []c=new char[arr.size()];
    
       for(int i=0;i<arr.size();i++)
       {
           c[i]=arr.get(i);
       }
        return new String(c);
        
       
    }
    */
}