--> Fire Game https://vjudge.net/problem/FZU-2150
直接写中文了
Descriptions:
两个熊孩子在 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;
- }
- }
来源: http://www.bubuko.com/infodetail-3110751.html