首页 > 代码库 > fzu2150（bfs）
fzu2150（bfs）
题目链接：http://acm.fzu.edu.cn/problem.php?pid=2150
题意：在任意两处点火，求最短时间烧光所有草堆。
分析：由于n,m比较小，将所有草堆坐标记录下来，然后暴力枚举所有可能的两处草堆为起点燃烧。最后取最短时间。求每两处燃烧需要用的时间一次bfs即可。
#include <cstdio>#include <cstring>#include <cmath>#include <iostream>#include <algorithm>#include <queue>#include <cstdlib>#include <vector>#include <set>#include <map>#define LL long long#define mod 1000000007#define inf 0x3f3f3f3f#define N 100010using namespace std;struct node{ int x,y,step;};int vis[15][15],n,m;char s[15][15];int px[110],py[110],tot;int dx[]={0,0,1,-1};int dy[]={1,-1,0,0};queue<node>que;node make_node(int a,int b,int c){ node temp; temp.x=a;temp.y=b;temp.step=c; return temp;}bool judge(int x,int y){ return x>=1&&x<=n&&y>=1&&y<=m&&s[x][y]==‘#‘&&!vis[x][y];}int bfs(int i,int j){ memset(vis,0,sizeof(vis)); while(!que.empty())que.pop(); que.push(make_node(px[i],py[i],0)); que.push(make_node(px[j],py[j],0)); vis[px[i]][py[i]]=1;vis[px[j]][py[j]]=1; int sum=0,mx=0; while(!que.empty()) { node cur,nxt; cur=que.front();que.pop(); int step=cur.step; mx=max(step,mx); sum++; for(int ii=0;ii<4;ii++) { int x=dx[ii]+cur.x,y=dy[ii]+cur.y; if(judge(x,y)) { vis[x][y]=1; que.push(make_node(x,y,step+1)); } } } if(sum==tot)return mx; else return inf;}int main(){ int T,cas=1; scanf("%d",&T); while(T--) { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++)scanf("%s",s[i]+1); tot=0; for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) if(s[i][j]==‘#‘) { px[++tot]=i;py[tot]=j; } } printf("Case %d: ",cas++); if(tot<=2) { puts("0");continue; } int ans=inf; for(int i=1;i<=tot;i++) for(int j=i+1;j<=tot;j++) { ans=min(ans,bfs(i,j)); } if(ans==inf)puts("-1"); else printf("%d\n",ans); }}
fzu2150（bfs）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。