首页 > 代码库 > search2049
search2049
题目大意：有一个迷宫，在迷宫中有墙与门
有m道墙，每一道墙表示为(x,y,d,t）
x,y表示墙的起始坐标
d为0即向右t个单位，都是墙
d为1即向上t个单位，都是墙
有n道门，每一道门表示为(x,y,d)
x,y表示门的起始坐标
d为0即向右一个单位表示门
d为1即向上一个单位表示门
再给出你起点的位置(f1,f2)，并保证这个点的位置不会再墙或者门中，为起点到(0,0)最少要穿过多少条门
在地图类的题目中，BFS和DFS的区别在于前者每步都知道一定是正确的，而后者本质上是一种尝试，如果错误，那么回朔回来。这个跟贪心、DP的区别类似。前者每步都是正确的，后者每一步不保证是正确的，所以要遍历所有情况。
搜索题，我的做法是用优先队列（保证当前所通过的门是最少的），所以遇见出口，就可以直接得到结果，
/凡是进队的，按照穿过门数从小到的顺序重新排列队列这样可以保证获得的结果是最小的，关于优先队列，代码的后面有详细说明。
这里一定用优先队列，而不是普通的队列，因为需要保证先进队比后进队列的 所经过的门数要少，所以要按门数排列。如果不是因为门数这个特殊权限，直接用普通队列即可。这里如果不按门数排列次序，那么排在队列前面的虽然经过的步长最少，但是经过的门数不一定最少
如下图，如果目标对于红色3的位置，按照普通队列的BFS，则从下面的2走到3路径短，但是可能经过了1个门，而如果从上面这条路走，虽然走的路比较远，但
可能一个门都不用经过。因此按照门数排序，就可以保证从上面这条路
走而不是下面的这条路(红色3只能被走一次)。因此不能用普通队列
哪怕用普通队列对各个解比较，取最小值（因为最优解的路
可能被次优解用过了，每条路的顶点只能用一次）
每次从队列出来的（肯定都是目前门数最小的）都查看是否已经
达到目标，如果是，即为最优解。
搜索从Nemo的位置开始，有三种情况，遇见门，door加1，入队，遇见air，直接入队，遇见墙，continue；
我的存储结构见代码，
这里还要注意两点，一是Nemo的位置可能超出[1--199],所以开始时有必要进行判断（因为这，n个runtime error ，郁闷了几个小时。。）二是这个如果用C++提交的话，好像输入Nemo的位置时，必须用cin（不能用scanf，当然G++也可以通过的），这是偶然在discuss上看到的，要不，不知又要郁闷多久。。。
#include<stdio.h>#include<queue>using namespace std;int map[2][250][250],posi[250][250];//我用小方形的左下的坐标表示这个小方形（譬如，Nemo的坐标为（1.5,1.5），则他所在的小方形为（1,1）），posi[i][j]指i,j点是否已经被访问，map[0][i][j]为坐标为（i,j），平行于x轴的一个墙（或门，空气），map[1][i][j]则为平行于y轴的typedef struct nn{int x; friend bool operator<(struct nn n1,struct nn n2)//重载优先队列的比较仿函数 { return n1.door > n2.door;//凡是进队的，按照穿过门数从小到的顺序重新排列队列这样可以保证获得的结果是最小的， }int y,door;}po;//door记录了到达小方形（i,j）所通过的最少门数，int main(void){int i,j,n,m,x,y,d,t,tx,ty,td,flag,door,txx,tyy,maxx,maxy,minx,miny;int dd[4]={0,1,1,0},xx[4]={0,0,1,0},yy[4]={0,0,0,1},xxx[4]={0,-1,1,0},yyy[4]={-1,0,0,1};//dd[]指到某个方形后可去的四个方向，我是按下、左、右、上的顺序，xx[],yy[],xxx[],yyy[]与之对应，xx[],yy[]指去这个方向时要通过的边的坐标（map[][][]），xxx,yyy指通过边后到达的新的小方形的坐标（posi[][]）,double f1,f2;po tem;priority_queue<po>q;while(scanf("%d%d",&m,&n)!=EOF){ if(m==-1&&n==-1) break; for(i=0;i<201;i++) for(j=0;j<=200;j++) { posi[i][j]=0; map[0][i][j]=0; map[1][i][j]=0;//0指为air } maxx=maxy=-20; minx=miny=220; while(m--) { scanf("%d%d%d%d",&x,&y,&d,&t); for(i=0;i<t;i++) map[d][x+i*(1-d)][y+i*d]=1;//1指墙 按左下角存储 if(x<minx) minx=x; if(y<miny) miny=y; if(x>maxx) maxx=x; if(y>maxy) maxy=y; } while(n--) { scanf("%d%d%d",&x,&y,&d); map[d][x][y]=2;//2指door } scanf("%lf%lf",&f1,&f2); x=(int)f1; y=(int)f2; if(x<minx||y<miny||x>=maxx||y>=maxy) //在墙之外，一个门都不用穿越 直接得到 { printf("0\n"); continue; } while(!q.empty()) q.pop(); tem.x=x; tem.y=y; tem.door=0; q.push(tem); flag=0; posi[x][y]=1; while(!q.empty()) { tem=q.top(); q.pop(); x=tem.x; y=tem.y; door=tem.door; if(x>=maxx||x<minx||y>=maxy||y<miny)//走出墙之外则出去了。 { flag=1; break; } for(i=0;i<4;i++) { 移、上移一个单位。如上图 ty=yy[i]+y; txx=xxx[i]+x;//四个方向的各个下一个访问点 tyy=yyy[i]+y; if(map[td][tx][ty]==2&&posi[txx][tyy]==0)//遇到门 { tem.x=txx; tem.y=tyy; tem.door=door+1; posi[txx][tyy]=1;//该点已经被访问 q.push(tem); } if(map[td][tx][ty]==0&&posi[txx][tyy]==0)//什么障碍也没有 { posi[txx][tyy]=1;//该点已经被访问 tem.x=txx; tem.y=tyy; tem.door=door; q.push(tem); } } } if(flag==1) printf("%d\n",door); else printf("-1\n");}}
search2049