leetcode第79题（中等）

原链接：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

解题思路

算法：深度优先搜索，回溯，递归

1.遍历该网格的所有节点

2.每遍历一个节点，就从该节点开始，遍历与他相邻的上下左右四个节点，如果遍历到第n个节点并满足第n个节点与word[n]的值对应则继续递归遍历该节点的相邻节点。直到word的所有值都相同返回true。如果不满足第n个节点与word[n]的值对应则回溯上一个节点继续遍历其他相邻。

代码（java）

class Solution {
    public boolean exist(char[][] board, String word) {
        return has(board,word);
    }
    
    public static boolean has(char[][] board, String word) {
        c=word.toCharArray();
        height=board.length;
        width=board[0].length;
        boards=board;
        index=new boolean[height][width];
        for(int i=0;i<board.length;i++){
            for (int j=0;j<board[i].length;j++){
                if(dfs(i,j,0)){
                    return true;
                }
            }
        }
        return false;
    }
    public static char[][] boards;
    public static boolean[][] index;
    public static char[] c;
    public static int width;
    public static int height;
    //方位增量
    public static int[][] local={{0,-1},{-1,0},{0,1},{1,0}};
    public static boolean dfs(int i,int j,int def){
        if(c[def]==boards[i][j]){
            if((def+1)==c.length){
                return true;
            }
            for(int k=0;k<4;k++){
                int i0=i+local[k][0];
                int j1=j+local[k][1];
                if(i0>=0&&i0<height&&j1>=0&&j1<width&&!index[i0][j1]){
                    index[i][j]=true;
                    if(dfs(i0,j1,def+1)){
                        index[i][j]=false;
                        return true;
                    }
                    index[i][j]=false;
                }
            }
        }else{
            return false;
        }
        return false;
    }
}