// 记录起点,然后dfs

class Solution {

    int[] dx = {-1 , 0, 1, 0};
    int[] dy = {0, 1, 0, -1};
    int n;
    int m;
    boolean[][] vis;
    public boolean exist(char[][] board, String word) {

        List<Integer> row = new ArrayList<>();
        List<Integer> col = new ArrayList<>();
        n = board.length;
        m = board[0].length;

        int count = 0;
        for (int i = 0;i < n; i++){
            for (int j = 0 ; j < m; j++){
                if (board[i][j] == word.charAt(0)){
                    row.add(i);
                    col.add(j);
                    count++;
                }
            }
        }
        vis = new boolean[n][m];
        for (int i = 0;i < count; i++){

            for (int j = 0;j < n; j++){
                Arrays.fill(vis[j], false);
            }
            if (dfs(board,row.get(i), col.get(i), word, 0)){
                return true;
            }
        }
        return false;
    }

    public boolean dfs(char[][] board, int x, int y, String word, int len){
        vis[x][y] = true;
        if (len == word.length() - 1) {
            if (board[x][y] == word.charAt(len))
                return true;
            return false;
        }
        boolean flag = false;
        for (int i = 0;i < 4; i ++){
            int tx = x + dx[i];
            int ty = y + dy[i];
            if (ok(tx,ty) && board[x][y] == word.charAt(len) && !vis[tx][ty]) {
                if (dfs(board,tx,ty, word, len + 1)){
                    flag = true;
                    return true;
                }
            }
        }
        vis[x][y] = false;
        return flag;
    }

    public boolean ok(int tx,int ty) {
        if (tx >= 0 && tx < n && ty >= 0 && ty < m){
            return true;
        }
        return false;
    }
}