一.题目
题目分析:要求我们在一个二维矩阵中寻找一个单词,如果找到返回true，找不到返回false
这道题用dfs和bfs都可以解决,都是通过遍历所有结果，来查询
代码如下：
class Solution {public static int[] dx = {0,1,0,-1};public static int[] dy = {1,0,-1,0};//右，下，左，上public boolean exist(char[][] board, String word) {boolean[][] mark = new boolean[board.length][board[0].length];String s = "";if (board == null || board.length == 0 || word == null || word.length() == 0) {return false;}for(int i = 0;i<board.length;i++){for(int j = 0;j<board[i].length;j++){if(board[i][j]==word.charAt(0)){int index = 0;if(dfs(i,j,word,board,mark,index+1))return true;}}}return false;}public static boolean dfs(int x,int y,String word,char[][] bord,boolean[][] mark,int index){if(index==word.length())return true;mark[x][y] = true;for(int i = 0;i<4;i++){int xx = x + dx[i];int yy = y + dy[i];if(cheak(xx,yy,mark)){if(bord[xx][yy] == word.charAt(index)){if(dfs(xx,yy,word,bord,mark,index+1))return true;}}}mark[x][y] = false;return false;}public static boolean cheak(int x,int y,boolean[][] mark)//减枝{if(x<0||x>=mark.length||y<0||y>=mark[0].length||mark[x][y]==true)return false;return true;}
}首先定义方向向量，来进行上下左右四个方向的搜素，遍历整个二维数组，如果对应的下标是单词的首个字母，那么就进行dfs遍历从当前位置的所有可能
为什么将dfs的返回值定义为boolean类型？
1.一开始错误在于将dfs返回值定义为int类型，定义为int是因为index是基本数据类型，无法在传参过程中改变index的值，后面想着用int作为返回值，又犯了一个错，在递归回溯过程中，有可能没有递归到最后一个结果就提前return了
如图所示，返回的可能是中间值
四个方向都不通，返回的是错误结果，递归没有遍历全部
2.错误2将访问过的条件语句写错位置
3.错误3没有对临界值进行处理
cheak作用是减枝，避免不必要的递归
dfs算法核心:
1.确定递归结束语句，题目要求的答案位置
2.进行递归的位置，符合题目的约束条件
3.回溯语句写在哪里（递归之后）
5.想清楚回溯和方法的条件语句
4.参数的传递，像递归这种操作，最好将参数传递进行，不要使用全局变量，很容易在递归中发生错误，很难找
5.减枝，减少时间复杂度，避免不必要的递归