题目链接
https://leetcode.com/problems/word-search/
解题思路
dfs
代码
int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
class Solution {
public:
bool exist(vector<vector<char>>& board, string word) {
if (board.empty()) {
return true;
}
vector<vector<bool>> mark(board.size(), vector<bool>(board[0].size(), false));
for (int i = 0; i < board.size(); ++i) {
for (int j = 0; j < board[i].size(); ++j) {
if (dfs(board, mark, i, j, word, 0)) {
return true;
}
}
}
return false;
}
bool dfs(vector<vector<char>>& board, vector<vector<bool>> &mark, int n, int m, string &word, int p) {
if (board[n][m] == word[p]) {
if (word.length() == p + 1) {
return true;
}
mark[n][m] = true;
for (int i = 0; i < 4; ++i) {
int n1 = n + dir[i][0], m1 = m + dir[i][1];
if (n1 < 0 || n1 >= board.size() || m1 < 0 || m1 >= board[0].size()) {
continue;
}
if (!mark[n1][m1] && dfs(board, mark, n1, m1, word, p + 1)) {
return true;
}
}
mark[n][m] = false;
}
return false;
}
};
