注意取消标记，感觉本质上就是一种回溯

class Solution {
    public boolean exist(char[][] board, String word) {

        boolean res = false;
        int chang = board[0].length;
        int kuan = board.length;

        // 新建辅助数组帮助判断某个位置是否已经走过
        boolean[][] flags = new boolean[kuan][chang];

        // 从每个位置开始尝试遍历word
        for (int i = 0; i < kuan; i++) {
            for (int j = 0; j < chang; j++) {
                if (searchWord(board, i, j, chang, kuan, word, 0, flags)) {
                    res = true;
                    return res;
                }
            }
        }

        return res;
    }

    public boolean searchWord(char[][] borad, int i, int j, int chang, int kuan, String word, int index, boolean[][] flags) {
        // base case
        if (index>=word.length()) {
            return true;
        }
        if (i<0 || i>=kuan || j<0 || j>=chang || flags[i][j]==true || borad[i][j]!= word.charAt(index) ) {
            return false;
        }

        // 访问到该位置时flag设为true
        flags[i][j] = true;

        // 上右下左四个方向遍历
        boolean res = searchWord(borad, i-1, j, chang, kuan, word, index+1, flags) ||
                searchWord(borad, i, j+1, chang, kuan, word, index+1, flags) ||
                searchWord(borad, i+1, j, chang, kuan, word, index+1, flags) ||
                searchWord(borad, i, j-1, chang, kuan, word, index+1, flags);

        // 递归回退时flag置为初始状态false  重要！！！！！！！
        flags[i][j] = false;  
        return res;
    }

}