【FZU - 2150】Fire Game(bfs)
--> Fire Game
直接写中文了
Descriptions:
SRE实战 互联网时代守护先锋,助力企业售后服务体系运筹帷幄!一键直达领取阿里云限量特价优惠。两个熊孩子在n*m的平地上放火玩,#表示草,两个熊孩子分别选一个#格子点火,火可以向上向下向左向右在有草的格子蔓延,点火的地方时间为0,蔓延至下一格的时间依次加一。求烧完所有的草需要的最少时间。如不能烧完输出-1。
Input
第一行,输入一个T,表示有T组测试数据。 每组数据由一个n,m分别表示行列
1 <= T <=100, 1 <= n <=10, 1 <= m <=10
Output
输出最少需要的时间Sample Input
4 3 3 .#. ### .#. 3 3 .#. #.# .#. 3 3 ... #.# ... 3 3 ### ..# #.#
Sample Output
Case 1: 1 Case 2: -1 Case 3: 0 Case 4: 2
题目链接:
https://vjudge.net/problem/FZU-2150
感觉还是有一定难度的,肯定是要从两个地方开始dfs的,这两个地方一定是干草,同时这两个地方可以重叠,那么就直接把所有的干草全部列举出来,每次取两个去dfs,然后取这些dfs的最小值即可,具体操作看代码
AC代码
#include <iostream> #include <cstdio> #include <fstream> #include <algorithm> #include <cmath> #include <deque> #include <vector> #include <queue> #include <string> #include <cstring> #include <map> #include <stack> #include <set> #include <sstream> #define mod 1000000007 #define eps 1e-6 #define ll long long #define INF 0x3f3f3f3f #define ME0(x) memset(x,0,sizeof(x)) using namespace std; int T,n,m,total,cnt; char mp[15][15];//原始地图 int vis[15][15];//记录是否烧过 int dt[][2]= {{1,0},{-1,0},{0,1},{0,-1}};//方向 struct node { int x,y;//横纵坐标 int step;//步数 }; node now,next; node a[15*15];//干草坐标 bool judge()//判断草地是否全部烧完 { for(int i=0; i<total; i++) if(!vis[a[i].x][a[i].y]) return false; return true; } int bfs(node a,node b) { int steps=0;//初始步数为0 ME0(vis); queue<node>q; q.push(a),q.push(b); vis[a.x][a.y]=1,vis[b.x][b.y]=1; while(!q.empty()) { now=q.front(); q.pop(); for(int i=0; i<4; i++)//分4个方向测试 { next.x=now.x+dt[i][0]; next.y=now.y+dt[i][1]; next.step=now.step+1; //是否满足条件 if(next.x>=0&&next.x<n&&next.y>=0&&next.y<m&&mp[next.x][next.y]=='#'&&!vis[next.x][next.y]) { vis[next.x][next.y]=1; steps=max(steps,next.step); q.push(next); } } } if(judge())//判断 return steps; else return INF; } int main() { cnt=1;//第几组测试数据 cin>>T; while(T--) { total=0;//有多少干草 cin>>n>>m; for(int i=0; i<n; i++) { for(int j=0; j<m; j++) { cin>>mp[i][j]; if(mp[i][j]=='#')//把干草存入数组 { a[total].x=i; a[total].y=j; a[total++].step=0; } } } int ans=INF; for(int i=0; i<total; i++) { for(int j=i; j<total; j++) { ans=min(bfs(a[i],a[j]),ans);//每次都取步数最小的值 } } // for(int i=0; i<total; i++) // cout<<a[i].x<<" "<<a[i].y<<endl; printf("Case %d: ",cnt++); if(ans==INF) cout<<-1<<endl; else cout<<ans<<endl; } }
更多精彩