Leetcode之回溯法专题-79. 单词搜索（Word Search）
给定一个二维网格和一个单词，找出该单词是否存在于网格中。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
示例:
board =
[
['A','B','C','E'],
['S','F','C','S'],
['A','D','E','E']
] 给定 word = "ABCCED", 返回 true.
给定 word = "SEE", 返回 true.
给定 word = "ABCB", 返回 false.
分析：
给定一个地图，求一个经过一段路径后（上、下、左、右）能否形成给定的单词。
一题很经典的地图+回溯类型的题，题中需要一个vis数组来控制地图是否已走过，
来确保不走回头路。
vis[x][y]=1 时 则之前走过，不走。
vis[x][y]=0 则表示之前未走过，可以走。 AC代码：
class Solution {
boolean flag = false;
int dirx[] = new int[]{1,-1,0,0};
int diry[] = new int[]{0,0,1,-1};
public boolean exist(char[][] board, String word) {
if(board.length==0 || word.equals("")){
return false;
}
char first = word.charAt(0);
for(int i=0;i<board.length;i++){
for(int j=0;j<board[0].length;j++){
if(board[i][j]==first){
int vis[][] = new int[board.length][board[0].length];
vis[i][j] = 1;
dfs(board,vis,i,j,word,1);
vis[i][j] = 0;
}
}
}
return flag;
}
public void dfs(char[][] board,int vis[][],int x,int y,String word,int now){
if(now == word.length()){
flag = true;
return;
}
if(flag) return;
int m = board.length;
int n = board[0].length;
for(int i=0;i<4;i++){
int xx = x + dirx[i];
int yy = y + diry[i];
if(xx>=0 && xx<m && yy>=0 && yy<n && vis[xx][yy]==0 && board[xx][yy]==word.charAt(now)){
vis[xx][yy] = 1;
dfs(board,vis,xx,yy,word,now+1);
vis[xx][yy] = 0;
}
}
}
}