🦄个人主页:修修修也
🎏所属专栏:刷题
⚙️操作环境:牛客网
目录
一.单词搜索
题目详情:
题目思路:
解题代码:
结语
一.单词搜索
牛客网题目链接(点击即可跳转):NC242 单词搜索
题目详情:
本题详情如下图:
题目思路:
本题解题思路如下:
对二维数组的每一个位置都dfs一下,如果找到完整的单词就返回true,如果全部找完都没找到就返回false.
主函数的逻辑是bfs完每一个二维数组里符合第一个字母的位置,如果找到就返回找到了,没找到就找下一个符合的,遍历完还没找到就返回false.
bfs的逻辑是,从当前位置开始搜索四个方位有没有符合下一个字母的,如果有,进去递归下一个字母,如果没有,返回当前路径失败,退回寻找下一路径.
一定要记得字母不可以重复使用,所以每到一个位置就要锁一个位置!如果该位置被弃用则要释放锁.
解题代码:
本题解题代码如下:
class Solution { public:int vis[101][101]={0};//标记这个位置是否被用过int dx[4]={0,0,1,-1};int dy[4]={1,-1,0,0};bool exist(vector<string>& board, string word) {//遍历二维数组,找到第一个字符,然后广度优先搜索for(int i=0;i<board.size();i++){for(int j=0;j<board[0].size();j++){if(board[i][j] == word[0]) if(bfs(board,word,0,i,j)==true) return true;//有一次成了就返回true}}return false;//没一次成功,返回false}bool bfs(vector<string>& board,string& word,int pos,int x,int y){//如果递归到单词的最后一个字母,结束返回trueif(pos == word.size()-1) return true;//进入这个位置就把这个位置锁住vis[x][y] = 1;//如果递归的是中间字符,继续搜索4个方位有没有符合下一个的,如果有,继续递归搜for(int i=0; i<4; i++){int a = x+dx[i],b=y+dy[i];if(a>=0 && a<board.size() && b>=0 && b<board[0].size() && !vis[a][b] && board[a][b]==word[pos+1])if(bfs(board,word,pos+1,a,b))return true;}//如果四个位置找完没有符合下一个字符的,那么释放本位置的锁,返回falsevis[x][y]=0;return false;} };
结语
说点啥好呢...牵扯二维的算法就有点难了,但其实边界照常处理就行,一维的循环在n内,二维的两层循环在x,y内,不要去想的那么麻烦,二维其实就是机械化的处理一批一维数据罢了,还有不要抗拒递归,你想象它就是二叉的一个分支,你只要考虑你这个结点的前和后就行了,不要去管别的路径情况啥样,每个结点和分支都管好自己,最后就可以把准确的结果送达顶端.
