题解 | #矩阵中的路径#

     简单分享一下我对这个题的思路吧，本人学艺不精，如果有路过的大牛能帮助优化的话就更好了。
以本题示例为例：[[a,b,c,e],[s,f,c,s],[a,d,e,e]],"abcced"
[a,b,c,e]
[s,f,c,s ]
[a,d,e,e]
     我们需要先再矩阵中找到头字符，在头字符的位置开始向四周遍历。 （刚开始没仔细看题，只从头开始，后来才发现）

import java.util.*;


public class Solution {
    public static boolean hasPath(char[][] matrix, String word) {
        if(matrix.length==0||matrix[0].length==0)
            return false;
        if(matrix.length==1){
            if(Arrays.toString(matrix[0]).contains(word))
                return true;
        }
        List<String> lt=find(matrix,word.charAt(0));
        if(lt.size()==0)
            return false;
        try {
            for (String s : lt) {
                String[] split = s.split(",");
                int i=Integer.parseInt(split[0]);
                int j=Integer.parseInt(split[1]);
                go(matrix,word,new boolean[matrix.length][matrix[0].length],i,j,0);
            }
        }catch (Exception e){
            return true;
        }
        return false;
    }
    public static int go(char[][] matrix, String word, boolean[][] flag, int i, int j, int index) throws Exception {//i，j为传入的头字母的位置，index为查找到word的第n位
        if(index==word.length()){
            throw new Exception("true");
        }
        if(flag[i][j]||matrix[i][j]!=word.charAt(index)){
            return -1;
        }
        if(matrix[i][j]==word.charAt(index)){
            flag[i][j]=true;
            if(j+1<matrix[0].length){
                if(go(matrix,word,flag,i,j+1,index+1)==-1)
                    flag[i][j+1]=false;//回退修改过的flag数组
            }
            if(j-1>=0){
                go(matrix,word,flag,i,j-1,index+1);
                flag[i][j-1]=false;//回退修改过的flag数组
            }
            if(i+1<matrix.length){
                go(matrix,word,flag,i+1,j,index+1);
                flag[i+1][j]=false;//回退修改过的flag数组
            }
            if(i-1>=0){
                go(matrix,word,flag,i-1,j,index+1);
                flag[i-1][j]=false;//回退修改过的flag数组
            }
        }
        return -1;
    }
    public static List<String> find(char[][] matrix,char c){//查找并返回全部某一个字节是在矩阵的位置
        List<String> lt=new ArrayList<>();
        int[] result={-1,-1};
        for (int i=0;i<matrix.length;i++){
            for (int j=0;j<matrix[0].length;j++){
                if (matrix[i][j]==c){
                    String s=""+i+","+j;//用","隔开，防止存在多位数的i和j如，11和12，不知道准确的i与j位数的情况
                    lt.add(s);
                }
            }
        }
        return lt;
    }
}