您的位置:首页 > 新闻 > 资讯 > 天元建设集团有限公司是国企还是央企_门户网站开发_百度竞价推广方法_100种找客户的方法

天元建设集团有限公司是国企还是央企_门户网站开发_百度竞价推广方法_100种找客户的方法

2025/3/15 11:38:27 来源:https://blog.csdn.net/weixin_72357342/article/details/146242157  浏览:    关键词:天元建设集团有限公司是国企还是央企_门户网站开发_百度竞价推广方法_100种找客户的方法
天元建设集团有限公司是国企还是央企_门户网站开发_百度竞价推广方法_100种找客户的方法

🦄个人主页:修修修也

🎏所属专栏:刷题

⚙️操作环境:牛客网


目录

一.单词搜索

题目详情:

题目思路:

解题代码:

结语


一.单词搜索

牛客网题目链接(点击即可跳转):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内,不要去想的那么麻烦,二维其实就是机械化的处理一批一维数据罢了,还有不要抗拒递归,你想象它就是二叉的一个分支,你只要考虑你这个结点的前和后就行了,不要去管别的路径情况啥样,每个结点和分支都管好自己,最后就可以把准确的结果送达顶端.

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com