题解 | #矩阵中的路径#

dfs

import java.util.*;


public class Solution {
    boolean flag;
    boolean[][] visited;
    public boolean hasPath (char[][] matrix, String word) {
        visited = new boolean[matrix.length][matrix[0].length];
        flag = false;
        for(int i = 0;i<matrix.length;i++){
            for(int j = 0;j<matrix[0].length;j++){
                if(word.charAt(0) == matrix[i][j]){
                    dfs(matrix,word,0,i,j);
                    if(flag == true){
                        return true;
                    }
                }
            }
        }
        return false;
    }
    private void dfs(char[][] matrix,String word,int index,int i,int j){
        if(word.charAt(index) == matrix[i][j] && visited[i][j] == false){
            visited[i][j] = true;
            if(index == word.length()-1){
                flag = true;
                return;
            }
            if(i-1>=0){
                dfs(matrix,word,index+1,i-1,j);
            }
            if(j+1<matrix[0].length){
                dfs(matrix,word,index+1,i,j+1);
            }
            if(i+1<matrix.length){
                dfs(matrix,word,index+1,i+1,j);
            }
            if(j-1>=0){
                dfs(matrix,word,index+1,i,j-1);
            }
            visited[i][j] = false;
        }
    }
}