// @Title: 单词搜索 (Word Search)
// @Author: qisiii
// @Date: 2024-09-21 19:31:27
// @Runtime: 2177 ms
// @Memory: 43.9 MB
// @comment: 
// @flag: 
class Solution {
    boolean flag = false;

    public boolean exist(char[][] board, String word) {
        boolean[][] color = new boolean[board.length][board[0].length];
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (board[i][j] != word.charAt(0)) {
                    continue;
                }
                dfs(board, color, new StringBuilder(), word, i, j);
            }
        }
        return flag;
    }

    private void dfs(char[][] board, boolean[][] color, StringBuilder sb, String word, int x, int y) {
        if (sb.length() == word.length() && sb.toString().equals(word)) {
            flag = true;
            return;
        }
        if (x < 0 || y < 0 || x >= board.length || y >= board[0].length) {
            return;
        }
        if (flag || color[x][y]) {
            return;
        }
        if (sb.length() > word.length()) {
            return;
        }
        color[x][y] = true;
        sb.append(board[x][y]);
        dfs(board, color, sb, word, x + 1, y);
        dfs(board, color, sb, word, x - 1, y);
        dfs(board, color, sb, word, x, y + 1);
        dfs(board, color, sb, word, x, y - 1);
        color[x][y] = false;
        sb.deleteCharAt(sb.length() - 1);
    }
}