题目描述
bfs模板
样例
blablabla
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
#include<vector>
using namespace std;
const int N = 100;
int d[N][N];
int g[N][N];
int t,n,m;
typedef pair<int,int>PII;
vector<PII>res;
int bfs(PII a,PII b){
memset(d,-1,sizeof d);
queue<PII>q;
q.push(a);
if(a!=b)q.push(b);//避免重复
int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};
//初始化两个点的值
d[a.first][a.second]=d[b.first][b.second]=0;
int cnt = 0, maxt = 0;//cnt记录点燃的草地个数
//bfs模板
while(q.size()){
auto t=q.front();
q.pop();
for(int i=0;i<4;i++){
int x=t.first+dx[i],y=t.second+dy[i];
if(x>=0&&x<n&&y>=0&&y<m&&d[x][y]==-1&&g[x][y]){
d[x][y]=d[t.first][t.second]+1;
q.push({x,y});
maxt = max(maxt, d[x][y]);
}
}
cnt++;
}
if(cnt==(int)res.size())return maxt;
return -1;
}
int main(){
cin>>t;
int k=1;
while(t--){
res.clear();
cin>>n>>m;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
char c;
cin>>c;
if(c=='#')g[i][j]=1,res.push_back({i,j});
else g[i][j]=0;
}
}
//判断是否没有草坪
if(!(int)res.size()){
cout<<"Case "<<k++<<": "<<-1<<endl;
continue;
}
//定义最小值
int minx=2e9;
//循环找两个点
for(int i=0;i<(int)res.size();i++){
for(int j=i;j<(int)res.size();j++){
int tmp=bfs(res[i],res[j]);//循环搜索
if(tmp!=-1)minx=min(minx,tmp);
}
}
if(minx==2e9)minx=-1;
cout<<"Case "<<k++<<": "<<minx<<endl;
}
}
这个人也配过?
快去直你的播