首页 > 代码库 > POJ 3026-Borg Maze
POJ 3026-Borg Maze
题目链接:Borg Maze
日,终于过了,对这题,无力多说,没想到还有那样的数据,不搜题解,我八辈子也过不了,最小生成树的最后一题!
题意:就是 S 是初始点,A是外星人,构造一条路线使他们都能到达,且路线长度最短;
思路:1.求距离->(BFS) 2. 构图(小数据:邻接矩阵) 3.建树(Prim)
水题,难的是 POJ后台。
没看别人题解,不知道加gets()
#include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> const int N = 110; const int Size = 1<<20; const int INF = 65535; using namespace std; char a[N][N]; int n,m,mapp[N][N]; int dis[150],l; struct Node{ int xx,yy; }ver[Size]; struct node{ int x,y,ans; }q[Size]; int mv[4][2] = {{1,0},{0,1},{-1,0},{0,-1}}; void init() { for(int i = 0;i<l;i++) { mapp[i][i] = 0; } } void Prim() { int sum = 0,minn,pos; bool visp[150]; memset(visp,0,sizeof(visp)); for(int i = 0;i<l;i++) dis[i] = mapp[0][i]; dis[0] = 0; visp[0] = true; for(int i = 0;i<l;i++) { minn = INF; for(int j = 0;j<l;j++) { if(!visp[j] && dis[j]<minn) { minn = dis[j]; pos = j; } } if(minn!=INF) sum += minn; visp[pos] = true; for(int k = 0;k<l;k++) { if(!visp[k] && dis[k]>mapp[pos][k]) dis[k] = mapp[pos][k]; } } printf("%d\n",sum); } void BFS(int x,int y,int pos) { bool vis[N][N]; node f,t; memset(vis,0,sizeof(vis)); int s = 0,e = 0; f.x = x; f.y = y; f.ans = 0; q[e++] = f; vis[x][y] = true; while(s < e) { t = q[s++]; // printf("%d %d->",t.x,t.y); for(int i = 0;i<4;i++) { f.x = t.x + mv[i][0]; f.y = t.y + mv[i][1]; if(!vis[f.x][f.y] && 0<=f.x && f.x<m && 0<=f.y && f.y<n && a[f.x][f.y]!='#') { f.ans = t.ans + 1; if(a[f.x][f.y]=='A' || a[f.x][f.y]=='S') { for(int j = 0;j<l;j++) { if(ver[j].xx==f.x && ver[j].yy==f.y) mapp[pos][j] = f.ans; } } q[e++] = f; vis[f.x][f.y] = true; } } } } int main() { int T; // std::ios::sync_with_stdio(false); scanf("%d",&T); char b[100]; while(T--) { l = 0; //scanf("%d%d%*c",&n,&m); 1个%*c不够,据说后台是一串空格 scanf("%d%d",&n,&m); gets(b); //不加这个你永远过不了 for(int i = 0;i<m;i++) { gets(a[i]); for(int j = 0;j<n;j++) { if(a[i][j]=='A' || a[i][j]=='S') { ver[l].xx = i; ver[l++].yy = j; } } } init(); for(int i = 0;i<l;i++) { BFS(ver[i].xx,ver[i].yy,i); //枚举所有点到其他店的距离,构造 连通图 } /* for(int i = 0;i<l;i++) { for(int j = 0;j<l;j++) { if(mapp[i][j]==INF) printf("* "); else printf("%d ",mapp[i][j]); } printf("\n"); }*/ Prim(); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。