​ 话不多说，直接上题目链接，79.单词搜索 。题目描述如下：

题目思路

​       这是一道典型的 DFS （深度优先搜索）的题目，深度优先搜索的精髓就是递归，从某个节点开始遍历其邻近的节点，如果邻近的节点被访问过就不再访问，如果邻近的节点没有被访问过，那么就访问邻近的节点，这里的邻近指的是相邻的意思。然后再访问邻近节点的邻近节点，知道节点全部被访问才结束。这是一种图的遍历的方法，与之相对的还广度优先搜索 BFS ，关于广度优先搜索在下一次题目讲解中将会介绍。

       那么这道题我们就用 DFS 来做，首先我们要构造一个深度优先搜索的函数，来对输入的二维网格进行遍历。题目要求是要找到在网格中是否有给定 word 的匹配。我们知道一个 word 里有很多个字母，我们要一个字母一个字母的匹配。而在题目要求：

​       也就是说，假如我们在二维数组board [i] [j] 里找到了一个字母和 word 的首字母匹配，然后匹配的第二个字母必须是这个board [i] [j] 的上下左右间距为1，如果没有就返回1。

​       所以我们的思路就很清晰了，首先遍历题目所给 word ，并在二维网格里找到能够匹配到 word 的第一个字母的坐标，然后在这个坐标下，进行上下左右的移动和试探，试图找到能够与 word 的第二个字母匹配的坐标，如果找到了，再在找到的坐标进行上下左右的移动，识图找到能够与 word 第三个字母匹配的坐标。如果找到了继续进行下去，如果没有找到，那么这次匹配失败，再找能够与 word 首字母匹配的坐标。

代码解释

• 方向数组：用来存储每次 x , y 坐标是如何变化的，比如说 dir[0] [0] 的值就是0，也就是说横坐标变化为0，dir[0] [1] 的值为 -1 也就是说纵坐标变化为 -1 ,也就是说dir[0] 表示的是横坐标不变，纵坐标减一，也就是向上运动一格的操作。dir数组的一维大小为 4 表示 上下左右四个方向。
• 访问数组：visted ，用来存储元素是否被访问，数组大小和二维网格 board 的大小是一样的。访问置1，未被访问置0。
• index：表示遍历到的 word 里单词的下标，初始值设为1，表示 word 的第一个字母能够在二维网格中找到，就算没有找到直接返回false，与 index 无关，只有在二维网格中找到了 word 的第一个字母，那么就进行dfs，这个时候 index 才起到作用。
• 每次遍历都是一种尝试，只有此次尝试成功才能返回 true ,如果此次返回不成功，那么相应的访问数组要恢复原来未被访问，也就是置0。
• dfs 遍历的时候要注意边界，比如说二维网格的右上角只能向左或者向下进行遍历，不能够向右或者向上进行遍历。所以每次坐标变换的时候要判断这个坐标是否有效，有效我们才能继续进行遍历。

代码

class Solution {
    
    //方向数组
    public static int[][] dir = {
    {
    0,-1},{
    0,1},{
    -1,0},{
    1,0}};
    //从单词的第一个字母开始
    public static int index = 0;
    //访问数组 用来存储元素是否被访问
    public static int[][] visted;
    public boolean exist(char[][] board, String word) {
    
        //特殊处理
        if(word==null || word.equals("")){
    
            return false;
        }
        //初始化visted数组
        int row = board.length;
        int col = board[0].length;
        visted = new int[row][col];
        //初始化index
        index = 1;
        //从图中匹配
        for(int i = 0;i<row;++i){
    
            for(int j = 0;j<col;++j){
    
                //如果未被访问而且匹配到单词的第一个字母
                if(visted[i][j]==0 && board[i][j]==word.charAt(0)){
    
                    visted[i][j] = 1;
                    //从这个字母开始进行第二个字母的匹配
                    if(dfs(i,j,1,word,board)){
    
                        return true;
                    }
                    visted[i][j] = 0;
                }
            }
        }
        return false;
    }

    //dfs 遍历
    public boolean dfs(int x,int y,int deep,String word,char[][] board){
    
        //获取单词长度
        int len = word.length();
        //获取二维网格的行和列
        int row = board.length;
        int col = board[0].length;
        //条件 当到单词末尾 并且最后一个字母也找到
        if(deep==len && board[x][y]==word.charAt(len-1)){
    
            return true;
        }

        //从四个方向上进行遍历
        for(int i = 0;i<4;++i){
    
            int tempx = x + dir[i][0];
            int tempy = y + dir[i][1];
            //边界条件
            if(tempx < 0 || tempy >= col || tempx >= row || tempy < 0 || visted[tempx][tempy]==1 || board[tempx][tempy]!=word.charAt(index)){
    
                continue;
            }else{
    
                //当前访问过的点置1
                visted[tempx][tempy] = 1;
                //匹配下一个字母
                index++;
                if(dfs(tempx,tempy,deep+1,word,board)){
    
                    return true;
                }
                //没有匹配到
                index--;
                visted[tempx][tempy] = 0;
            }
        }
        return false;
    }
}