【UVA 10307 Killing Aliens in Borg Maze】最小生成树, kruscal, bfs

题目链接：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=20846

POJ 3026是同样的题，但是内存要求比较严格，并是没有过。。。

对以迷宫形式给定的一些点求最小生成树，不过这里的边并不是抽象的两点间笛卡尔距离，也不是折线距离（迷宫中有障碍），而是需要用四个方向的搜索来求。

用bfs求出任两点间的最短距离后，可用kruscal求出最小生成树。

这次值得一提的是对并查集的一点改造：由于每个顶点由一组(x,y)坐标唯一确定，而并查集的元素应是能用一个整数唯一确定的，所以要将(x,y)坐标的集合映射到整数集合。联想到了最近课内学的信道的“分频复用”，和实时操作系统uCOS-II的任务就绪表的数据结构和算法。于是就有了如下做法，其实很常见了~

x,y坐标范围是[0,50]，50<2^6，因此可用一个int型（2^31）的低7位存y坐标，8~14位存x坐标，14<31，一个整型完全可以存下。这样一个点可由一个int型数(低14位)完全确定，并且以每维2^14为size开二维数组vis和dis也可以开下。

经检验这个做法可行，其实就是模仿底层，把基本型当作结构体看待，每位的语义是约定好的，自己编码自己解码~

代码在UVA过了（没限制内存），在POJ上还是MLE，待我好好补一补搜索再来更新吧~

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <cmath>
  4 #include <algorithm>
  5 #include <stack>
  6 #include <vector>
  7 #include <queue>
  8 using namespace std;
  9 const int MAX_S=55;
 10 const int MAX_N=105;
 11 struct Point
 12 {
 13     int x,y;
 14     Point(){}
 15     Point(int xx,int yy):x(xx),y(yy){}
 16 };
 17
 18 struct Edge
 19 {
 20     Point u,v;
 21     int w;
 22 }e[MAX_N*MAX_N];
 23 bool cmp(const Edge e1,const Edge e2)
 24 {
 25     return e1.w<e2.w;
 26 }
 27
 28 int par[(MAX_S<<7)+MAX_S];
 29 void init()
 30 {
 31     memset(par,-1,sizeof(par));
 32 }
 33 int find(int x)
 34 {
 35     if(par[x]==-1) return x;
 36     return par[x]=find(par[x]);
 37 }
 38 void unite(Point p1,Point p2)
 39 {
 40     int x=(p1.x<<7)+p1.y;
 41     int y=(p2.x<<7)+p2.y;
 42     x=find(x);
 43     y=find(y);
 44     if(x==y) return ;
 45     par[x]=y;
 46 }
 47
 48 bool same(Point p1,Point p2)
 49 {
 50     int x=(p1.x<<7)+p1.y;
 51     int y=(p2.x<<7)+p2.y;
 52     return find(x)==find(y);
 53 }
 54
 55 int T;
 56 int w,h;
 57 int n,m;
 58 char maze[MAX_S][MAX_S];
 59 int dx[]={0,0,1,-1},dy[]={1,-1,0,0};
 60
 61 typedef pair<Point,int> P;
 62 int vis[MAX_S][MAX_S];
 63 int dis[(MAX_S<<7)+MAX_S][(MAX_S<<7)+MAX_S];
 64
 65 void bfs(int x,int y)
 66 {
 67     int poi=(x<<7)+y;
 68     memset(vis,0,sizeof(vis));
 69     queue<P> que;//Point,step
 70     que.push(P(Point(x,y),0));
 71     vis[x][y]=1;
 72     while(!que.empty())
 73     {
 74         Point p=que.front().first;
 75         int step=que.front().second;
 76         que.pop();
 77         for(int i=0;i<4;i++)
 78         {
 79             int nx=p.x+dx[i];
 80             int ny=p.y+dy[i];
 81             int npoi=(nx<<7)+ny;
 82             if(nx<0||ny<0||w<=nx||w<=ny||vis[nx][ny]) continue;
 83             if(maze[nx][ny]=='#'){vis[nx][ny]=1; continue;}
 84             if(dis[poi][npoi]||poi==npoi) continue;
 85             que.push(P(Point(nx,ny),step+1));
 86             vis[nx][ny]=1;
 87             if((maze[nx][ny]=='A'||maze[nx][ny]=='S')&&poi!=npoi)
 88             {
 89                 e[m].u=Point(x,y);
 90                 e[m].v=Point(nx,ny);
 91                 dis[npoi][poi]=dis[poi][npoi]=e[m].w=step+1;
 92                 m++;
 93             }
 94         }
 95     }
 96 }
 97
 98 int kruscal()
 99 {
100     init();
101     int ans=0;
102     for(int i=0;i<m;i++)
103     {
104         if(!same(e[i].u,e[i].v))
105         {
106             unite(e[i].u,e[i].v);
107             ans+=e[i].w;
108         }
109     }
110     return ans;
111 }
112
113 int main()
114 {
115     freopen("3026.txt","r",stdin);
116     scanf("%d",&T);
117     while(T--)
118     {
119         scanf("%d%d",&w,&h);
120         n=0;
121         getchar();
122         for(int i=0;i<h;i++)
123         {
124             fgets(maze[i],w,stdin);
125             gets(maze[i+1]);
126         }
127         m=0;
128         memset(dis,0,sizeof(dis));
129         for(int i=0;i<h;i++)
130         {
131             for(int j=0;j<w;j++)
132                 if(maze[i][j]=='A'||maze[i][j]=='S') bfs(i,j);
133         }
134 /*
135        for(int i=0;i<m;i++)
136            printf("%d %d -> %d %d = %d\n",e[i].u.x,e[i].u.y,e[i].v.x,e[i].v.y,e[i].w);
137 */
138         sort(e,e+m,cmp);
139         printf("%d\n",kruscal());
140     }
141     return 0;
142 }