【POJ 3026】Borg Maze

一個考察隊搜索alien 這個考察隊能夠無限切割 問搜索到全部alien所須要的總步數 即求一個無向圖 包括全部的點而且總權值最小(最小生成樹

BFS+最小生成樹

Prim/Kruskal…懶死了 就這么貼吧……湊活看(￣┰￣*)

#include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> #include <queue> #include <algorithm> #define INF 0x3f3f3f3fusing namespace std;typedef struct Point { int x,y; }Point;typedef struct Edge { int u,v,w; bool operator < (const struct Edge a)const { return w < a.w; } }Edge;Edge eg[10100]; bool vs[101][101]; Point p[101]; char mp[51][52]; int id[51][51]; int dis[101][101]; bool vis[51][51]; //int dss[101]; //bool vs[101]; int dirx[] = { 0, 0, 1,-1}; int diry[] = { 1,-1, 0, 0}; int ds[51][51]; int tp,x,y,top; int pre[101];void Bfs(int xx,int yy) { memset(vis,0,sizeof(vis)); queue <pair<int,int> > q; q.push(pair<int,int> (xx,yy)); vis[xx][yy] = 1; ds[xx][yy] = 0; int i,aa,bb,a,b; while(!q.empty()) { pair <int,int> pt = q.front(); q.pop(); a = pt.first; b = pt.second; for(i = 0; i < 4; ++i) { aa = a+dirx[i]; bb = b+diry[i]; if(aa > x || bb > y || aa < 1 || bb < 1 || mp[aa][bb] == '#' || vis[aa][bb]) continue; ds[aa][bb] = ds[a][b]+1; vis[aa][bb] = 1; q.push(pair<int,int> (aa,bb)); // if(mp[aa][bb] != ' ') dis[id[xx][yy]][id[aa][bb]] = dis[id[aa][bb]][id[xx][yy]] = ds[aa][bb]; if(mp[aa][bb] != ' ' && !vs[id[xx][yy]][id[aa][bb]]) { vs[id[xx][yy]][id[aa][bb]] = vs[id[aa][bb]][id[xx][yy]] = 1; eg[top].u = id[xx][yy]; eg[top].v = id[aa][bb]; eg[top++].w = ds[aa][bb]; } } } }void Init(int n) { int i; for(i = 0; i < n; ++i) pre[i] = i; }int Find(int x) { if(x != pre[x]) pre[x] = Find(pre[x]); return pre[x]; }//int Prim() //{ // memset(vs,0,sizeof(vs)); // memset(dss,INF,sizeof(dss)); // dss[0] = 0; // int i,j,p,w,sum = 0; // for(i = 0; i < tp; ++i) // { // w = INF; // for(j = 0; j < tp; ++j) // { // if(!vs[j] && w > dss[j]) // { // w = dss[j]; // p = j; // } // } // sum += w; // vs[p] = 1; // for(j = 0; j < tp; ++j) // { // if(!vs[j] && dss[j] > dis[p][j]) // dss[j] = dis[p][j]; // } // } // return sum; //}int main() { int n,i,j; int cnt,sum,k,r; scanf("%d",&n); while(n--) { memset(vs,0,sizeof(vs)); tp = top = 0; scanf("%d %d",&y,&x); gets(mp[0]); for(i = 1; i <= x; ++i) { gets(mp[i]+1); for(j = 1; mp[i][j]; ++j) { if(mp[i][j] != '#' && mp[i][j] != ' ') { id[i][j] = tp; p[tp].x = i; p[tp++].y = j; } } } Init(tp); for(i = 0; i < tp; ++i) { Bfs(p[i].x,p[i].y); } // printf("%d\n",Prim()); sort(eg,eg+top); sum = cnt = 0; for(i = 0; i < top; ++i) { k = Find(eg[i].u); r = Find(eg[i].v); if(k != r) { pre[k] = r; sum += eg[i].w; cnt++; } if(cnt == tp) break; } printf("%d\n",sum); } return 0; } /*BFS+Prim*///Memory Time //368K 0MS#include<iostream> #include<string> #include <cstdlib> #include <cstdio> #include <cstring> using namespace std;const int inf=2501; //無限大,最大迷宮的總長也就2500char map[51][51]; //迷宮原圖 int node[51][51]; //記錄當前格是否為字母，是第幾個字母 int col,row; //當前迷宮的行列數 int num; //字母頂點數數目 int dist[102][102]; //構造結點圖的兩結點間權值。理論結點數最多為2500個（每個同意通行的格為一個結點）//可是POJ的數據庫同意壓縮到101個，哈哈，這樣時間和空間復雜度都降低非常多 int edge[102][102]; //構造字母圖的兩個字母間的邊權，字母數最多為101class move {public:int row,col; }mov[4]={{0,-1},{0,1},{-1,0},{1,0}}; //分別相應 上 下 左 右void bfs(int i,int j) {bool vist[51][51]; //標記當前迷宮某一格是否已被訪問int que_x[2500],que_y[2500]; //坐標隊列int head=0,tail=0; //隊列指針/*Initial*/memset(dist,0,sizeof(dist));memset(vist,false,sizeof(vist));vist[i][j]=true;que_x[tail]=i;que_y[tail++]=j;while(head<tail){int x=que_x[head];int y=que_y[head++];if(node[x][y])edge[ node[i][j] ][ node[x][y] ] = dist[x][y]; //抽取字母到字母的邊權for(int k=0;k<4;k++){int mx=x+mov[k].row;int my=y+mov[k].col;if(mx>=1 && mx<= row && my>=1 && my<=col)if(!vist[mx][my] && map[mx][my]!='#'){que_x[tail]=mx;que_y[tail++]=my;vist[mx][my]=true;dist[mx][my]=dist[x][y]+1;}}}return; }int prim(void) {int s=1;int m=1;bool u[102];u[s]=true;int min_w;int prim_w=0;int point;int low_dis[102];for(int i=1;i<=num;i++){low_dis[i]=inf;u[i]=false;}while(true){if(m==num)break;min_w=inf;for(int i=2;i<=num;i++){if(!u[i] && low_dis[i]>edge[s][i])low_dis[i] = edge[s][i];if(!u[i] && min_w>low_dis[i]){min_w=low_dis[i];point=i;}}s=point;u[s]=true;prim_w+=min_w;m++;}return prim_w; }int main(int i,int j) {int test;cin>>test;while(test--){/*Initial*/memset(node,0,sizeof(node));num=0;/*Input*/cin>>col>>row;char temp[51];gets(temp); //吃掉cin遺留下來的換行符,我不知道為什么getchar()會AWfor(i=1;i<=row;i++){gets(map[i]);for(j=1;j<=col;j++)if(map[i][j]=='A'||map[i][j]=='S')node[i][j]=++num;}/*BFS-> Structure Maps*/for(i=1;i<=row;i++)for(j=1;j<=col;j++)if(node[i][j])bfs(i,j); //構造結點i,j到其它全部結點的邊權（非#的格子就是一個結點）/*Prim Algorithm & Output*/cout<<prim()<<endl;}return 0; }

總結

以上是生活随笔為你收集整理的【POJ 3026】Borg Maze的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。