class Solution {
public:
bool exist(vector<vector<char>>& board, string word) {
if(board.size()==0||board[0].size()==0) return word.empty();
for(int i=0; i<board.size(); i++){
for(int j=0; j<board[0].size(); j++){
if(dfs(board,word,i,j,0)) return true;
}
}
return false;
}
bool dfs(vector<vector<char>> &board, string &word,int x, int y,int now){
if(x>=board.size()||x<0||y>=board[0].size()||y<0) return false;
if(now==word.length()-1&&word[now]==board[x][y]) return true;
if(word[now]!=board[x][y]) return false;
board[x][y] = ' ';
if(dfs(board,word,x-1,y,now+1)) return true;
if(dfs(board,word,x+1,y,now+1)) return true;
if(dfs(board,word,x,y-1,now+1)) return true;
if(dfs(board,word,x,y+1,now+1)) return true;
board[x][y] = word[now];
return false;
}
};
dfs+回溯
判斷空的時候用empty很巧妙，省去了多個if
回溯的理由：目前點不是我想走的，我沒走，就沒必要清空，要複原