79.单词搜索

题目描述：

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

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

　　示例:

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

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

题解：

public class L79 {
    static Boolean resflag = false;
    static int[] dx = {1,0,-1,0},dy = {0,-1,0,1};
    public static boolean exist(char[][] board, String word) {
        resflag = false;
        if (board == null || board.length == 0){return false;}
        char[] wordChar = word.toCharArray();
        boolean[][] flag = new boolean[board.length][board[0].length];
        for(int boardX = 0;boardX<board.length;boardX++){
            for(int boardY = 0;boardY < board[0].length;boardY ++){
                if(board[boardX][boardY] == wordChar[0]){
                    flag[boardX][boardY] = true;
                    backExist(board,1,wordChar, flag,boardX,boardY);
                    //结果为true，直接返回，否则继续遍历 
                   if(resflag)return true;
                   flag[boardX][boardY] = false;

            }
        }
        }
    return false;
    }
    private static void backExist(char[][] board, int index, char[] wordChar, boolean[][] flag, int x, int y) {
        if(resflag || index == wordChar.length){
            resflag = true;
            return;
        }
        //该步骤的判断是为了进行剪枝的操作，即目标完成后进行返回
        for(int i=0;i<4;i++){
                int X_next = x + dx[i];int Y_next = y + dy[i];
                //不可以超出边界
                if(X_next>=0 && Y_next>=0 & X_next< board.length & Y_next< board[0].length){
                    if (!(flag[X_next][Y_next]) && board[X_next][Y_next] == wordChar[index]){
                        flag[X_next][Y_next] = true;
                        backExist(board,index+1,wordChar, flag, X_next,Y_next);
                        flag[X_next][Y_next] = false;
                    }
                }
            }
        return;
    }
    public static void main(String[] args) {
        char[][] board = {{'A','B','C','E'},{'S','F','E','S'},{'A','D','E','E'}};
        String word = "ABCESEEEFS";
        Boolean x = exist(board,  word);
        System.out.println(x);
    }
}