深度优先搜索+回溯解决网格问题

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

        char[] words = word.toCharArray();
        int[][] flag = new int[board.length][board[0].length];
        for(int i = 0; i < board.length; i++){
            for(int j = 0; j < board[0].length; j++){
                if(dfs(board, i, j, words, 0, flag)){
                    return true;
                }
            }
        }
        return false;
    }

    public boolean dfs(char[][] board, int r, int c, char[] words, int len, int[][] flag){
        if(r < 0 || r >= board.length || c < 0 || c >= board[0].length || words[len] != board[r][c] || flag[r][c] == 1){
            return false;
        }
        //终止条件
        if(len == words.length - 1){
            return true;
        }
        //进行标记
        flag[r][c] = 1;
        //回溯
        if(dfs(board, r+1, c, words, len+1, flag) || dfs(board, r, c+1, words, len+1, flag) || dfs(board, r-1, c, words, len+1, flag) || dfs(board, r, c-1, words, len+1, flag))
            return true;
        //进行撤销
        flag[r][c] = 0;
        return false;
    }
}