1. 全栈程序员必看首页

AcWing 2060. 奶牛选美（bfs+dfs）

全栈程序员-站长 • • 未分类 • 阅读 2

AcWing 2060. 奶牛选美（bfs+dfs）题目 2060 奶牛选美题解 dfs 分别找到两块区域 并且用 1 2 标记他们 然后从第一块区域开始 bfs 将所有非第一块区域的点 且向外走一步的距离 放进队列 q 里 最后再对队列 q 里的点进行 dfs 第一个出现的标记为 2 的点时 输出其 dis 即可 注意 bfs 里的标记最好插入到队列的时候就标记 当然还是得看需求 比如优先队列的时候就不是这样 所以以后用 bfs 的时候要注意插入与标记的顺序 include bits stdc h definexfirst defineys bits

题目：2060. 奶牛选美

在这里插入图片描述
在这里插入图片描述
题解：dfs分别找到两块区域，并且用1、2标记他们，然后从第一块区域开始bfs，将所有非第一块区域的点（且向外走一步的距离）放进队列q里。最后再对队列q里的点进行dfs，第一个出现的标记为2的点时，输出其dis即可。
注意：bfs里的标记最好插入到队列的时候就标记。当然还是得看需求，比如优先队列的时候就不是这样。所以以后用bfs的时候要注意插入与标记的顺序！！！






#include 
     #define x first #define y second using namespace std; typedef pair<int ,int > PII; const int N=1e6+10; const int mod=1e9; char a[55][55]; int n,m; int sta[55][55],dis[55][55]; int fx[4]={ 
   0,0,-1,1},fy[4]={ 
   1,-1,0,0}; queue<PII> qu; void dfs(int x,int y,int fg){ 
    sta[x][y]=fg; for(int i=0;i<4;i++){ 
    int xx=x+fx[i],yy=y+fy[i]; if(xx<0||xx>=n||yy<0||yy>=m) continue; if(sta[xx][yy]||a[xx][yy]=='.') continue; dfs(xx,yy,fg); } } int bfs(){ 
    bool state[55][55]; memset(state,0,sizeof state); queue<PII> q; PII t1=qu.front(); state[t1.x][t1.y]=1; while(qu.size()){ 
    PII t=qu.front(); qu.pop(); for(int i=0;i<4;i++){ 
    int xx=t.x+fx[i],yy=t.y+fy[i]; if(xx<0||xx>=n||yy<0||yy>=m) continue; if(state[xx][yy]) continue; if(sta[xx][yy]==1){ 
    state[xx][yy]=1; qu.push({ 
   xx,yy}); }else{ 
    state[xx][yy]=1; dis[xx][yy]=1; q.push({ 
   xx,yy}); } } } while(q.size()){ 
    PII t=q.front(); q.pop(); if(sta[t.x][t.y]==2) return dis[t.x][t.y]; for(int i=0;i<4;i++){ 
    int xx=t.x+fx[i],yy=t.y+fy[i]; if(xx<0||xx>=n||yy<0||yy>=m) continue; if(state[xx][yy]) continue; dis[xx][yy]=dis[t.x][t.y]+1; state[xx][yy]=1; q.push({ 
   xx,yy}); } } } int main(){ 
    cin>>n>>m; for(int i=0;i<n;i++) cin>>a[i]; memset(sta,0,sizeof sta); int fg=1; for(int i=0;i<n;i++){ 
    for(int j=0;j<m;j++){ 
    if(!sta[i][j]&&a[i][j]=='X'){ 
    if(fg==1){ 
    qu.push({ 
   i,j}); } dfs(i,j,fg); fg++; } } } cout<<bfs()-1; return 0; }
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。

发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/227147.html原文链接：https://javaforall.net

赞 (0)
0 0

关于作者

全栈程序员-站长的头像

全栈程序员-站长

133.5K 文章
3 粉丝
本网站汇聚当前互联网主流语音，持续更新，欢迎关注公众号“全栈程序员社区”
上一篇 2026年3月16日 下午9:50
下一篇 2026年3月16日 下午9:50


相关推荐

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

关注全栈程序员社区公众号