y总方法(备忘)
图dfs + 偏移量
C++ 代码
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[0].size(); j ++){
if(dfs(board, word, 0, i, j)) return true;
}
}
return false;
}
bool dfs(vector<vector<char>>& matrix, string& str, int u, int x, int y){
if(matrix[x][y] != str[u])return false;
if(u == str.size() - 1)return true;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
char t = matrix[x][y];
matrix[x][y] = '*';
for(int i = 0; i < 4; i ++ ){
int a = x + dx[i], b = y + dy[i];
if(a < 0 || a >= matrix.size() || b < 0 || b >= matrix[0].size())
{
continue;
}
if(dfs(matrix, str, u + 1, a, b)) return true;
}
matrix[x][y] = t;
return false;
}
};