LeetCode 79. 单词搜索
原题链接
中等
作者:
bruce
,
2021-01-27 17:26:29
,
所有人可见
,
阅读 243
class Solution {
public:
bool exist(vector<vector<char>>& board, string word) {
for(int i=0;i<board.size();i++)
{
for(int j = 0;j<board[i].size();j++)
{
if(dfs(board, word, 0, i, j)) return true;
}
}
return false;
}
bool dfs(vector<vector<char>>&board, string &word, int start, int x, int y)
{
if(board[x][y] != word[start]) return false;
if(start == word.size()-1) return true;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
char t = board[x][y];
board[x][y] = '.';
for(int i = 0; i<4; i++)
{
int a = dx[i] + x, b = dy[i] + y;
if(a<0 || a >= board.size() || b < 0 || b>=board[0].size() || board[a][b]=='.') continue;
if(dfs(board, word, start+1, a, b)) return true;
}
board[x][y] = t;
return false;
}
};