自己免费做网站,中国建筑有限公司西南分公司网页设计,成都捕鱼网站建设,html5线上运营网站leetCode79. 单词搜索 思路#xff1a;就是在各个位置四个方向的暴力搜索#xff08;dfs#xff09;#xff0c;直到找到word一摸一样的方案为止 代码
/*
此题就是一个从每一个方向向四周暴力搜索的题目
*/
class Solution {
public:bool exist(vectorvectorchar就是在各个位置四个方向的暴力搜索dfs直到找到word一摸一样的方案为止 代码
/*
此题就是一个从每一个方向向四周暴力搜索的题目
*/
class Solution {
public:bool exist(vectorvectorchar board, string word) {for(int i 0; i board.size(); i){for(int j 0; j board[0].size(); j){// 表示从i,j)开始搜索且从word[0]开始匹配if(dfs(board,word,0,i,j)) return true;}}return false;}int dx[4] {0, 1, 0, -1};int dy[4] {1, 0, -1, 0}; bool dfs(vectorvectorchar board, string word, int u, int x, int y){if(word[u] ! board[x][y]) return false;if(u word.size() - 1) return true;char temp board[x][y];board[x][y] .; // 表示该位置已经走过不能走了// 朝四个方向开始搜索for(int i 0; i 4; i){int x1 x dx[i];int y1 y dy[i];// 如果遇到边界或者已经搜过的位置就这个方向的搜索停止if(x1 0 || x1 board.size() || y1 0 || y1 board[0].size() || board[x1][y1] .) continue;// 表示这个位置可以搜就继续往该位置搜if(dfs(board,word,u 1, x1, y1)) return true;} board[x][y] temp; // 回溯复原现场以免影响下一个位置的搜索且表示没有搜到解决方案返回falsereturn false;}
};
