LeetCode 79. 单词搜索
原题链接
中等
作者:
linux_2019
,
2019-09-14 07:31:20
,
所有人可见
,
阅读 1066
C++ 代码
class Solution {
public:
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
int n,m;
bool exist(vector<vector<char>>& board, string word) {
if(board.size()==0|| board[0].size()==0) return false;
n=board.size();
m=board[0].size();
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
if(dfs(board,i,j,0,word))
return true;
return false;
}
bool dfs(vector<vector<char>> & board,int i,int j,int u,string & word)
{
if(board[i][j]!=word[u]) return false;
if(u==word.size()-1)
{
return true;
}
board[i][j]='.';
for(int k=0;k<4;k++)
{
int a=i+dx[k],b=j+dy[k];
if(a>=0&&a<n && b>=0&&b<m)
if(dfs(board,a,b,u+1,word))
return true;
}
board[i][j]=word[u];
return false;
}
};