思路: 依次对单元格中每一个字母沿四个方向进行深度优先搜索,搜索中为防止字母重复使用,需维护一个标识字母是否已经被访问的visited数组,回溯完成。
class Solution {
public:
//搜索的四个方向
int dir[4][4]={{-1,0},{1,0},{0,1},{0,-1}};
bool exist(vector<vector<char>>& board, string word) {
int m=board.size();
int n=board[0].size();
//辅助数组,标识字母是否被访问
vector<vector<bool>>visited(m,vector<bool>(n,false));
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
//对每一个字母进行深度优先搜索
if(dfs(i,j,0,board,word,visited))
return true;
}
}
return false;
}
bool dfs(int x,int y,int index,vector<vector<char>>& board,string &word,vector<vector<bool>>&visited){
//递归结束条件,要考虑边界条件
if(index==word.size()-1) return board[x][y]==word[index];
if(board[x][y]==word[index]){
visited[x][y]=true;
//四个方向进行搜索
for(int i=0;i<4;i++){
int new_x=x+dir[i][0];
int new_y=y+dir[i][1];
if(new_x>=0&&new_x<board.size()&&new_y>=0&&new_y<board[0].size()&&!visited[new_x][new_y])
if(dfs(new_x,new_y,index+1,board,word,visited))
return true;
}
visited[x][y]=false;
}
return false;
}
};