单词搜索

题目来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/word-search

给定一个二维网格和一个单词，找出该单词是否存在于网格中。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

示例:

board =
[
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]

给定 word = "ABCCED", 返回 true.
给定 word = "SEE", 返回 true.
给定 word = "ABCB", 返回 false.

深度优先遍历解法：

class Solution {
    public boolean exist(char[][] board, String word) {
        if(board.length*board[0].length < word.length())
            return false;
        for (int i = 0;i<board.length;i++){
            for (int j= 0;j<board[0].length;j++){
                int[][] book = new int[board.length][board[0].length];
                book[i][j] = 1;
                if(dfs(board,0,word,i,j,book))
                    return true;
                book[i][j] = 0;
            }
        }
        return false;
    }

    private int[] getNext(int i){
        //右下左上
        int[][] next = {{0,1},{1,0},{0,-1},{-1,0}};
        return next[i];
    }

    private boolean dfs(char[][] board,int step,String word,int x,int y,int[][] book){
        if (step >= word.length() || board[x][y] != word.charAt(step))
            return false;
        if (step == word.length() -1){
            //说明匹配上了
            return true;
        }
        //尝试四个方向
        for(int i=0;i<4;i++){
            int[] next = getNext(i);
            int nextX = x + next[0];
            int nextY = y + next[1];
            //判断是否越界和是否走过
            if (nextX < 0 || nextX >= board.length || nextY<0 || nextY>=board[0].length || book[nextX][nextY] == 1)
                continue;
            //可以走
            //标记已经走过
            book[nextX][nextY] = 1;
            if(dfs(board,step+1,word,nextX,nextY,book))
                return true;
            //取消标记
            book[nextX][nextY] = 0;
        }
        return false;
    }
}