12 矩阵中的路径

示例 1：

输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
输出：true

示例 2：

输入：board = [["a","b"],["c","d"]], word = "abcd"
输出：false

class Solution {
    public boolean exist(char[][] board, String word) {
        char first=word.charAt(0);
        boolean[][] visited=new boolean[board.length][board[0].length];
        for(int i=0;i<board.length;++i){
            for(int j=0;j<board[i].length;++j){
                if(first==board[i][j]){
                    if(dfs(board, visited, word, 1, i, j)) return true;
                }
            }
        }
        return false;
    }

    private boolean dfs(char[][] board, boolean[][] visited, String word, int index, int i, int j){
        if(index==word.length()) return true;
        visited[i][j] = true;
        char next=word.charAt(index);
        if(i-1>=0 && !visited[i-1][j] && next==board[i-1][j]){
            if(dfs(board, visited, word, index+1, i-1, j)) return true;
        }
        if(i+1<board.length && !visited[i+1][j] && next==board[i+1][j]){
            if(dfs(board, visited, word, index+1, i+1, j)) return true;
        }
        if(j-1>=0 && !visited[i][j-1] && next==board[i][j-1]){
            if(dfs(board, visited, word, index+1, i, j-1)) return true;
        }
        if(j+1<board[i].length && !visited[i][j+1] && next==board[i][j+1]){
            if(dfs(board, visited, word, index+1, i, j+1)) return true;
        }

        visited[i][j]=false;
        return false;

    }
}

牛客

请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子。例如

a b c e
s f c s
a d e e

矩阵中包含一条字符串"bcced"的路径，但是矩阵中不包含"abcb"路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入该格子。

示例1
输入：[[a,b,c,e],[s,f,c,s],[a,d,e,e]],"abcced"
返回值：true

示例2
输入：[[a,b,c,e],[s,f,c,s],[a,d,e,e]],"abcb"
返回值：false

深度优先搜索

import java.util.*;
 
 
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param matrix char字符型二维数组
     * @param word string字符串
     * @return bool布尔型
     */
    boolean [][] done;
    int width,height;
    public boolean hasPath (char[][] matrix, String word) {
                height=matrix.length;
        width=matrix[0].length;
        done=new boolean[height][width];
        char[] w=word.toCharArray();
        for(int i=0;i<height;++i) {
            for(int j=0;j<width;++j) {
                 
                if(hasPath(matrix,w,i,j,0))
                    return true;
            }
        }
        return false;
    }
    private boolean hasPath(char[][] matrix, char[] word, int i, int j,int index) {
        char c=word[index];
        if(c!=matrix[i][j]) {
            done[i][j]=false;
            return false;
        }
        done[i][j]=true;
        if(index<word.length-1) {
            if(i+1<height && !done[i+1][j])
                if( hasPath(matrix,word,i+1,j,index+1))
                    return true;
            if(i-1>=0 && !done[i-1][j])
                if( hasPath(matrix,word,i-1,j,index+1))
                    return true;
            if(j+1<width && !done[i][j+1])
                if( hasPath(matrix,word,i,j+1,index+1))
                    return true;
            if(j-1>=0 && !done[i][j-1])
                if( hasPath(matrix,word,i,j-1,index+1))
                    return true;
        } else {
            return true;
        }
        done[i][j]=false;
        return false;
    }
}