【USACO 2.4】Overfencing(bfs最短路)
2.4 BFS 短路 USACO
2023-09-11 14:19:25 时间
H行W列的迷宫,用2*H+1行的字符串表示,每行最多有2*W+1个字符,省略每行后面的空格。迷宫的边界上有且仅有两个出口,求每个点出发到出口的最短路。
+-+-+-+-+-+ | | +-+ +-+ + + | | | | + +-+-+ + + | | | +-+ +-+-+-+
以每个出口为起点bfs,需要注意的是,最后的距离是(d+1)/2。
/* TASK:maze1 URL:http://train.usaco.org/usacoprob2?a=iHr5iXglQfJ&S=maze1 LANG:C++ */ #include<cstdio> #include<algorithm> #include<cstring> #include<queue> #define N 305 using namespace std; int n,m,dx[5]={0,1,0,-1},dy[5]={1,0,-1,0},dis[N][N],ans,vis[N][N]; char c[N][N]; struct node { int x,y,d; }; queue<node>q; void bfs(){ for(int i=0;i<=2*m;i++) for(int j=0;j<=2*n;j++) if(!i||i==2*m||!j||j==2*n) if(!c[i][j]||c[i][j]==' '){ memset(vis,0,sizeof vis); q.push((node){i,j,0}); while(!q.empty()){ node t=q.front(); q.pop(); int x=t.x,y=t.y,d=t.d; if(vis[x][y]||x<0||y<0||x>2*m+1||y>2*n+1||c[x][y]&&c[x][y]!=' ')continue; vis[x][y]=1; dis[x][y]=min(dis[x][y],d); for(int i=0;i<=4;i++) q.push((node){x+dx[i],y+dy[i],d+1}); } } } int main(){ freopen("maze1.in","r",stdin); freopen("maze1.out","w",stdout); scanf("%d%d",&n,&m); for(int i=0;i<=m*2;i++) scanf("%*c%[^\n]",c[i]); memset(dis,0x3f3f3f3f,sizeof dis); bfs(); for(int i=1;i<=2*m;i+=2) for(int j=1;j<=2*n;j+=2) ans=max(ans,dis[i][j]); printf("%d\n",ans+1>>1); return 0; }
相关文章
- Linux系统安装Apache 2.4.6
- [DeeplearningAI笔记]卷积神经网络2.3-2.4深度残差网络
- 预测分析:R语言实现2.4 评估线性回归模型
- 《CUDA高性能并行计算》----2.4 推荐项目
- Spring Boot 2.4.0 正式发布!全新的配置处理机制,拥抱云原生!
- 《Linux/UNIX OpenLDAP实战指南》——2.4 OpenLDAP配置
- 《用于物联网的Arduino项目开发:实用案例解析》—— 2.4 Arduino Yún的无线连接(WiFi)
- 《C++入门经典(第6版)》——2.4 函数
- 《深入理解JavaScript》——2.4 JavaScript有什么好用的工具吗
- 《Java EE 7精粹》—— 2.4 异步支持
- 《UML面向对象设计基础》—第2章2.4节面向对象的益处