点火游戏
↑ 题目链接
题目
给定一个 \(N\) 行 \(M\) 列的方格矩阵。其中一部分方格是草地，其余部分是空地。草地能够被燃烧，空地不会。当某个草地在 \(t\) 时刻被点燃时，其上下左右四个方向的相邻方格中的草地方格也会在 \(t+1\) 时刻被点燃。
注意，空地方格无论如何都不可能被点燃。
现在，你可以选择最多两个草地，将它们点燃。
请你计算，使得所有草地都被点燃所需花费的最少时间。
输入格式
第一行包含整数 \(T\) ，表示共有 \(T\)组测试数据。
每组数据第一行包含两个整数 \(N,M\)
接下来 \(N\) 行，包含一个 \(N×M\) 的字符矩阵，# 表示草地，. 表示空地。
输出格式
每组数据输出一个结果，每个结果占一行。
结果表示为 Case x: y，其中 \(x\) 为组别编号（从 \(1\) 开始），\(y\) 点燃所有草地需要花费的最短时间。如果无法点燃所有草地或者所有方格都是空地则输出 −1
数据范围
\(1≤T≤100,1≤N,M≤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\) 搜索过程中更新最值即可
代码
#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef pair<int,int> PII;
const int N=15;
char g[N][N];
int d[N][N];
int dx[]={-1,0,1,0},dy[]={0,1,0,-1};
int n,m;
int cnt;
int maxv;
void bfs(int sx1,int sy1,int sx2,int sy2)
{
memset(d,-1,sizeof d);
queue<PII>q;
q.push({sx1,sy1});
q.push({sx2,sy2});
d[sx1][sy1]=0;
d[sx2][sy2]=0;
while(q.size())
{
auto t=q.front();
q.pop();
cnt++;//统计草地个数
for(int i=0;i<4;i++)
{
int a=t.x+dx[i],b=t.y+dy[i];
if(a<0||a>=n||b<0||b>=m||d[a][b]!=-1||g[a][b]=='.')continue;
d[a][b]=d[t.x][t.y]+1;
maxv=max(d[a][b],maxv);//每次搜索取距离最大值
q.push({a,b});
}
}
}
int main()
{
int T;
cin>>T;
for(int Case=1;Case<=T;Case++)
{
cin>>n>>m;
vector<PII>grass;
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
{
cin>>g[i][j];
if(g[i][j]=='#')grass.push_back({i,j});
}
int res=1e9;
if(grass.size()==1)res=0;//特判草地数量为1
//枚举两块草地
for(int i=0;i<grass.size();i++)
for(int j=i+1;j<grass.size();j++)
{
int sx1=grass[i].first,sy1=grass[i].second;
int sx2=grass[j].first,sy2=grass[j].second;
cnt=0,maxv=0;
bfs(sx1,sy1,sx2,sy2);
if(cnt==grass.size())
res=min(res,maxv);//所有情况取最小值
}
if(res==1e9)res=-1;
printf("Case %d: %d\n",Case,res);
}
return 0;
}