poj 2049
题目大意 从（0，0）出发，给定终点，黑色边是墙，白色是门，问最少穿过多少门能到达终点。
分析 一开始就把这道题当作一道普通的格子BFS问题在写，写着写着才发现要求穿过的门的最少数。实际上无论是求最小的步数还是最少穿过的门数，方法都是一样的。但这道题不能用普通队列，而应该用优先队列，其实普通队列就是优先队列的一个特殊情况，最小步数问题在入队的过程中就保证了按步数从小到大排列。针对这道题，以穿过的门数来维护一个优先队列然后进行BFS。
注意 这道题有一些细节需要处理 1.题目中给的目标位置是小数，如果用double储存注意精度损失，比如将1输入double类型再转换成Int就会变成0. 2.题目中的给的目标位置的坐标是[1,199]，但实际上好像会出现0的数据
总的来说，这道题还是不错的。 还好没有折腾太久=_=
#include<cstdio> #include<iostream> #include<cmath> #include<cstring> #include<cstdlib> #include<queue> using namespace std; const int INF=999999999; int M,N; int wall[500][500][3];//wall[][][0]表示与x轴平行,1表示与y轴平行 int door[500][500][3]; int bj[500][500];//bj[i][j]表示以i j为左下角的格子是否走过 int cnt[500][500]; int tx,ty;//目标位置的左下角坐标 struct Node { int x; int y; int t;//穿过门数 friend bool operator <(const Node &a,const Node &b ) { return a.t>b.t; } }; bool Is_Out(int x,int y) { if(x<0 || x>199 || y<0 || y>199)return 1; return 0; } void Bfs() { priority_queue<Node> Q; Node s; s.x=0;s.y=0;s.t=0; Q.push(s); int x,y,t; while(!Q.empty()) { Node temp=Q.top(); x=temp.x;y=temp.y;t=temp.t; //if(t!=0)cout<<x<<" "<<y<<" "<<t<<endl; if(x==tx && y==ty) { cout<<t<<endl; return ; } Q.pop(); if(!Is_Out(x+1,y) && bj[x+1][y]==0)//向右走 { if(door[x+1][y][1] || (!wall[x+1][y][1]) ) { Node temp2; temp2.x=x+1; temp2.y=y; if(door[x+1][y][1])temp2.t=t+1; else temp2.t=t; bj[x+1][y]=1; Q.push(temp2); } } if(!Is_Out(x-1,y) && bj[x-1][y]==0)//向左走 { if(door[x][y][1] || (!wall[x][y][1]) ) { Node temp2; temp2.x=x-1; temp2.y=y; if(door[x][y][1])temp2.t=t+1; else temp2.t=t; bj[x-1][y]=1; Q.push(temp2); } } if(!Is_Out(x,y+1) && bj[x][y+1]==0)//向上走 { if(door[x][y+1][0] || (!wall[x][y+1][0]) ) { Node temp2; temp2.x=x; temp2.y=y+1; if(door[x][y+1][0])temp2.t=t+1; else temp2.t=t; bj[x][y+1]=1; Q.push(temp2); } } if(!Is_Out(x,y-1) && bj[x][y-1]==0)//向下走 { if(door[x][y][0] || (!wall[x][y][0]) ) { Node temp2; temp2.x=x; temp2.y=y-1; if(door[x][y][0])temp2.t=t+1; else temp2.t=t; bj[x][y-1]=1; Q.push(temp2); } } } cout<<"-1"<<endl; } int main() { int x,y,d,t; while(scanf("%d%d",&M,&N)!=EOF) { memset(wall,0,sizeof(wall)); memset(door,0,sizeof(door)); memset(bj,0,sizeof(bj)); memset(cnt,0,sizeof(cnt)); if(M==-1 && N==-1)break; for(int i=1;i<=M;i++) { scanf("%d%d%d%d",&x,&y,&d,&t); for(int i=1;i<=t;i++){wall[x][y][d]=1;if(d==0)x++;else y++;} } for(int i=1;i<=N;i++) { scanf("%d%d%d",&x,&y,&d); door[x][y][d]=1; } float c1,c2; scanf("%f%f",&c1,&c2); tx=(int)c1; ty=(int)c2; if(tx<=0 || ty<=0 || ty>=199 || ty>=199){printf("0\n");continue;} Bfs(); } }