J - Borg Maze
2024-08-31 09:01:14
思路:bfs+最小生成树。
#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define MAXN 110
using namespace std;
int fa[MAXN];
struct nond{
int x,y,z;
}v[MAXN*MAXN];
struct none{
int x,y,z;
};
int dx[]={,-,,};
int dy[]={,,,-};
int t,n,m,tot,sum,ans,point;
int map[MAXN][MAXN],vis[MAXN][MAXN];
void bfs(int x,int y){
queue<none>que;none s;s.x=x;s.y=y;s.z=;
memset(vis,,sizeof(vis));vis[x][y]=;
que.push(s);int k=;
while(!que.empty()){
none now=que.front();
que.pop();
for(int i=;i<;i++){
int cx=now.x+dx[i];
int cy=now.y+dy[i];
int cz=now.z+;
if(cx>=&&cx<=n&&cy>=&&cy<=m&&map[cx][cy]>=&&!vis[cx][cy]){
if(map[cx][cy]>){ v[++tot].x=map[x][y];v[tot].y=map[cx][cy];v[tot].z=cz;k++; }
if(k==point) return ;
none tmm;tmm.x=cx;tmm.y=cy;tmm.z=cz;
vis[cx][cy]=;que.push(tmm);
}
}
}
}
int cmp(nond a,nond b){
return a.z<b.z;
}
int find(int x){
if(fa[x]==x) return x;
else return fa[x]=find(fa[x]);
}
int main(){
scanf("%d",&t);
char tmp[MAXN];
while(t--){
scanf("%d%d",&m,&n);
gets(tmp);
for(int i=;i<=n;i++){
for(int j=;j<=m;j++){
char x;scanf("%c",&x);
if(x=='#') map[i][j]=-;
else if(x==' ') map[i][j]=;
else map[i][j]=++point;
}
char c;scanf("%c",&c);
}
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
if(map[i][j]>) bfs(i,j);
sort(v+,v++tot,cmp);
for(int i=;i<=point;i++) fa[i]=i;
for(int i=;i<=tot;i++){
int dx=find(v[i].x);
int dy=find(v[i].y);
if(dx==dy) continue;
fa[dy]=dx;sum++;
ans+=v[i].z;
if(sum==point-) break;
}
cout<<ans<<endl;
ans=;tot=;sum=;point=;
}
}
最新文章
- iOS开发之Bug(持续更新)
- iframe 跨域相互操作
- EF:The provider did not return a ProviderManifest instance
- django 其他地址访问不了问题
- 使用jQuery+PHP+Mysql实现抽奖程序
- Qt的版本历史
- Maven之——坐标和依赖(上)
- 测试横竖屏切换时activity 的生命周期
- mysql语句:批量更新多条记录的不同值
- EF实体类配置总结
- Python正则表达式学习笔记
- android 实现银联刷卡机消费后,手动签名的功能
- js 读取xml文件
- Java和操作系统交互细节
- hdu 1160 FatMouse&#39;s Speed (最长上升子序列+打印路径)
- Coursera Deep Learning 2 Improving Deep Neural Networks: Hyperparameter tuning, Regularization and Optimization - week1, Assignment(Regularization)
- java.lang.NumberFormatException 错误及解决办法
- 基于 Dojo toolkit 实现 web2.0 的 MVC 模式
- linux系统Centos环境下搭建SVN服务器及权限配置
- 高通Trustzone and QSEE介绍