/**
1. dfs: 首先收集所有起点, 对所有起点进行dfs
2. 搜索顺序: 判断4个方向合法并向下扩展, 直到最深
3. 搜索状态: index,  || board, word, visit
4. 剪枝: ~
*/

class Solution {
    public boolean exist(char[][] board, String word) {
        List<Integer> roots = new ArrayList<>();
        char start = word.charAt(0);
        int n = board.length, m = board[0].length;
        boolean[][] visit = new boolean[n][m];
        for (int i = 0 ; i < n ; i ++){
            for (int j = 0; j < m ; j ++){
                if (board[i][j] != start) continue;
                for (int k = 0 ; k < n ; k++) Arrays.fill(visit[k], false);
                if (dfs(i, j, 0, visit, board, word)) return true;
            }
        }
        return false;
    }

    int[] dx = {0, 0, 1, -1};
    int[] dy = {1, -1, 0, 0};
    public  boolean dfs(int x ,int y, int depth, boolean[][] visit, char[][] board, String word){
        if (depth == word.length() - 1) return true;
        visit[x][y] = true;
        int n =  board.length ,m =  board[0].length;
        for (int i = 0; i < 4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (0 <= nx && nx < n && 0 <= ny && ny <m && !visit[nx][ny] && board[nx][ny] == word.charAt(depth+1)){
                if (dfs(nx, ny, depth + 1, visit, board, word)) return true;
            }
        }
        visit[x][y] = false;
        return false;
    }
}