题意：给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

解题思路

解法1：
1.分析题意，解决好像很简单，只需要用DFS or BFS 去搜索出来所有路径，然后判断路径是否包含结果字符串即可
2.但是容易超时，需要考虑，如何剪枝，这里我们把寻找到路径，作为flag存储起来，之后就不必要进行重新走了
3.DFS的重点在于，针对于每个位置，进行遍历前，需要将其状态值临时保存下来，然后标记为走过，等上下左右都走过之后，此位置状态值还原

解题遇到的问题

无

后续需要总结学习的知识点

无

##解法1
class Solution {
    boolean flag = false;

    public boolean exist(char[][] board, String word) {
        if (word == null) {
            return true;
        }

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

    private void dfs(char[][] board, char[] words, int i, int j, int m, int n,
            int k) {
        if (flag) {
            return;
        }
        // 越界处理,回退
        if (i < 0 || i >= m || j < 0 || j >= n || board[i][j] != words[k]) {
            return;
        }

        if (k == words.length - 1) {
            // 找到答案，标记，回退
            flag = true;
            return;
        }

        // 先标记，用于后面回退
        char c = board[i][j];
        // 千万别忘记这步，需要把标记位走过
        board[i][j] = '*';
        dfs(board, words, i, j - 1, m, n, k + 1);
        dfs(board, words, i + 1, j, m, n, k + 1);
        dfs(board, words, i, j + 1, m, n, k + 1);
        dfs(board, words, i - 1, j, m, n, k + 1);
        // 回退标记位
        board[i][j] = c;
    }

}