$$\color{Purple}{kuangbin题解目录}$$
描述
给定一个 $N$ 行 $M$ 列的方格矩阵。
其中一部分方格是草地,其余部分是空地。
草地能够被燃烧,空地不会。
当某个草地在 $t$ 时刻被点燃时,其上下左右四个方向的相邻方格中的草地方格也会在 $t+1$ 时刻被点燃。
注意,空地方格无论如何都不可能被点燃。
现在,你可以选择最多两个草地,将它们点燃。
请你计算,使得所有草地都被点燃所需花费的最少时间。
输入格式
第一行包含整数 $T$,表示共有 $T$ 组测试数据。
每组数据第一行包含两个整数 $N,M$。
接下来 $N$ 行,包含一个 $N \\times M$ 的字符矩阵,#
表示草地,.
表示空地。
输出格式
每组数据输出一个结果,每个结果占一行。
结果表示为 Case x: y
,其中 $x$ 为组别编号(从 $1$ 开始),$y$ 点燃所有草地需要花费的最短时间。如果无法点燃所有草地或者所有方格都是空地则输出 $\-1$。
数据范围
$1 \\le T \\le 100$,
$1 \\le N,M \\le 10$。
输入样例:
5
3 3
.#.
###
.#.
3 3
.#.
#.#
.#.
3 3
...
#.#
...
3 3
###
..#
#.#
3 3
...
...
...
输出样例:
Case 1: 1
Case 2: -1
Case 3: 0
Case 4: 2
Case 5: -1
思路
经典的bfs问题,此题可暴力枚举两个草地的情况(可能存在一个草堆的情况,在跑两重循环第二层应从$i$开始),无终止条件,在$bfs$跑完后判断当前燃烧的草堆的个数是否与所有的草堆个数相等,返回最长的时间,并每次取最小值.
代码
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstdio>
#define MAXN 15
using namespace std;
typedef pair<int,int> PII;
const int inf=0x3f3f3f3f;
int t,n,m,res,sum,vis[MAXN][MAXN];
char g[MAXN][MAXN];
struct node{
int x;
int y;
int step;
};
int dir[4][2]={{-1,0},{0,1},{1,0},{0,-1}};
int bfs(PII a,PII b)
{
queue<node> q;
memset(vis,0,sizeof(vis));
q.push({a.first,a.second,0});
if(a!=b)
q.push({b.first,b.second,0});
vis[a.first][a.second]=vis[b.first][b.second]=1;
int cnt=0,maxx=0;
while(q.size()>0)
{
node temp=q.front();
q.pop();
cnt++;
for(int i=0;i<=3;i++)
{
int dx=temp.x+dir[i][0],dy=temp.y+dir[i][1];
if(dx>=1&&dx<=n&&dy>=1&&dy<=m&&vis[dx][dy]==0&&g[dx][dy]=='#')
{
maxx=max(maxx,temp.step+1);
vis[dx][dy]=1;
q.push({dx,dy,temp.step+1});
}
}
}
if(cnt==sum)
return maxx;
return -1;
}
int main()
{
scanf("%d",&t);
int cas=1;
while(t--)
{
vector<PII> v;
res=inf;
sum=0;
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%s",g[i]+1);
for(int j=1;j<=m;j++)
if(g[i][j]=='#')
v.push_back({i,j}),sum++;
}
for(int i=0;i<sum;i++)
for(int j=i;j<sum;j++)//注意此处是i,不是i+1,它有可能只有一堆
{
int temp=bfs(v[i],v[j]);
if(temp!=-1)
res=min(res,temp);
}
if(res==inf)
printf("Case %d: -1\n",cas++);
else printf("Case %d: %d\n",cas++,res);
}
return 0;
}