1、前言

2、思路

这道题看似可以使用岛问题的思路，确实可以使用岛问题的思路。但是因为岛问题的思路改变字符后，后面需要恢复过来，因为不恢复过来有些 case 过不来。还有一点，单词必须依据相邻的顺序，其实就是这几个字符需要相邻即可。

所以使用传统的 bfs 思路，分别遍历当前点，以及当前点的周围四个点。

3、代码

public class Q79_Exist {

    public boolean exist(char[][] board, String word){
        if(board == null || board.length == 0 || word == null || word.length() == 0){
            return false;
        }

        int m = board.length, n = board[0].length;
        boolean[][] visited = new boolean[m][n];
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(dfs(board, i, j, 0, word, visited)){
                    return true;
                }
            }
        }

        return false;
    }

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

        return false;
    }

    public static void main(String[] args) {
        char[][] board = {
                {'B','A', 'D'},
                {'D','A', 'D'},
                {'D','C', 'D'}
                };
        String word = "AAB";

        System.out.println(new Q79_Exist().exist(board, word));
    }
}