【UVA 10307 Killing Aliens in Borg Maze】最小生成树, kruscal, bfs-阿里云开发者社区

开发者社区> helena_wang> 正文

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

简介: 题目链接:http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=20846 POJ 3026是同样的题,但是内存要求比较严格,并是没有过。
+关注继续查看

题目链接: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 }

 

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
阿里云服务器怎么设置密码?怎么停机?怎么重启服务器?
如果在创建实例时没有设置密码,或者密码丢失,您可以在控制台上重新设置实例的登录密码。本文仅描述如何在 ECS 管理控制台上修改实例登录密码。
8716 0
malloc,colloc,realloc内存分配,动态库,静态库的生成与调用
 1.在main方法里面直接定义一个非常大的数组的时候,可能会出现栈溢出:错误代码演示: #include&lt;stdio.h&gt; #include&lt;stdlib.h&gt; void main() {     int a[1024 * 1024];     int num = 100;     system("p
1210 0
阿里云服务器端口号设置
阿里云服务器初级使用者可能面临的问题之一. 使用tomcat或者其他服务器软件设置端口号后,比如 一些不是默认的, mysql的 3306, mssql的1433,有时候打不开网页, 原因是没有在ecs安全组去设置这个端口号. 解决: 点击ecs下网络和安全下的安全组 在弹出的安全组中,如果没有就新建安全组,然后点击配置规则 最后如上图点击添加...或快速创建.   have fun!  将编程看作是一门艺术,而不单单是个技术。
10541 0
visual studio 2015生成64位DLL文件
新建一个visual C ++  -&gt;win32项目 点击生成-&gt;配置管理器新建一个64位debug位平台 hello.cpp程序代码如下: #include "stdafx.h" #include "jni.h" #include "com_magc_jni_HelloWorld.h" JNIEXPORT void JNICALL Java_com_magc_jni_H
3119 0
开发界的“神笔码良”来了!从设计稿智能生成H5应用
脱离切图仔,3步从设计稿直接智能生成H5应用,2000个顶级域名免费领!
3143 0
阿里云ECS云服务器初始化设置教程方法
阿里云ECS云服务器初始化是指将云服务器系统恢复到最初状态的过程,阿里云的服务器初始化是通过更换系统盘来实现的,是免费的,阿里云百科网分享服务器初始化教程: 服务器初始化教程方法 本文的服务器初始化是指将ECS云服务器系统恢复到最初状态,服务器中的数据也会被清空,所以初始化之前一定要先备份好。
11450 0
阿里云服务器ECS登录用户名是什么?系统不同默认账号也不同
阿里云服务器Windows系统默认用户名administrator,Linux镜像服务器用户名root
3797 0
通过wsdl2java工具生成客户端段代码(wsdl2java -p cn.com.css.misps.graph.webservice.impl -d F:\src -all http://10.)
首先当前是从官网下载cxf组件. Java代码 http://cxf.apache.org/download.html  http://cxf.apache.org/download.html 下载后解压,在这里主要是用到解压后的bin目录中的wsdl2java.bat该批处理文件. 可以直接进入bin目下,运行wsdl2java,需要注意的他
1387 0
+关注
helena_wang
&quot;The master has failed more times than the beginner has even tried.&quot;
59
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
《2021云上架构与运维峰会演讲合集》
立即下载
《零基础CSS入门教程》
立即下载
《零基础HTML入门教程》
立即下载