poj 2049 Finding Nemo(优先队列+bfs)

题目：http://poj.org/problem?id=2049

题意：

有一个迷宫，在迷宫中有墙与门有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)最少要穿过多少条门

代码是根据网上大神的稍微改了一下，就交了

  1 #include <iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<cstdlib>
  5 #include<stack>
  6 #include<queue>
  7 #include<cmath>
  8 #include<algorithm>
  9 using namespace std;
 10 
 11 #define maxn 250
 12 #define inf 99999999
 13 struct node
 14 {
 15     int x;
 16     int y;
 17     int len;
 18     bool operator <(const node &a)const//运算符重载，就是根据len从小到大排序
 19     {
 20         return len>a.len;
 21     }
 22 };
 23 
 24 int n,m,sx,sy,xmax,ymax;
 25 int dis[maxn][maxn],h[maxn][maxn],l[maxn][maxn];
 26 
 27 priority_queue<node>q;
 28 void bfs()
 29 {
 30     int x,y;
 31     for(x=0; x<=xmax; x++)
 32     {
 33         for(y=0; y<=ymax; y++)
 34             dis[x][y]=inf;
 35     }
 36     while(!q.empty())q.pop();
 37     node pn;
 38     pn.x=0;
 39     pn.y=0;
 40     pn.len=0;
 41     dis[0][0]=0;
 42     q.push(pn);
 43     while(!q.empty())
 44     {
 45         pn=q.top();
 46         q.pop();
 47         x=pn.x;
 48         y=pn.y;
 49         if(x==sx&&y==sy)return ;   //向上走
 50         if(y+1<=ymax&&dis[x][y+1]>dis[x][y]+h[x][y+1])
 51         {
 52             dis[x][y+1]=dis[x][y]+h[x][y+1];
 53             pn.x=x;
 54             pn.y=y+1;
 55             pn.len=dis[x][y+1];
 56             q.push(pn);
 57         }
 58         if(y-1>=0&&dis[x][y-1]>dis[x][y]+h[x][y])//向下走
 59         {
 60             dis[x][y-1]=dis[x][y]+h[x][y];
 61             pn.x=x;
 62             pn.y=y-1;
 63             pn.len=dis[x][y-1];
 64             q.push(pn);
 65         }
 66         if(x-1>=0&&dis[x-1][y]>dis[x][y]+l[x][y])//向左走
 67         {
 68             dis[x-1][y]=dis[x][y]+l[x][y];
 69             pn.x=x-1;
 70             pn.y=y;
 71             pn.len=dis[x-1][y];
 72             q.push(pn);
 73         }
 74         if(x+1<=xmax&&dis[x+1][y]>dis[x][y]+l[x+1][y])//向右走
 75         {
 76             dis[x+1][y]=dis[x][y]+l[x+1][y];
 77             pn.x=x+1;
 78             pn.y=y;
 79             pn.len=dis[x+1][y];
 80             q.push(pn);
 81         }
 82     }
 83     dis[sx][sy]=-1;
 84 }
 85 
 86 int main()
 87 {
 88     int i,j,x,y,d,t;
 89     double tx,ty;
 90     while(scanf("%d%d",&n,&m)!=EOF)
 91     {
 92         if(m==-1&&n==-1)break;
 93         xmax=ymax=-1;
 94         memset(h,0,sizeof(h));
 95         memset(l,0,sizeof(l));
 96         for(i=0; i<n; i++)
 97         {
 98             scanf("%d%d%d%d",&x,&y,&d,&t);
 99             if(d==0)
100             {
101                 for(j=0; j<t; j++)
102                 {
103                     h[x+j][y]=inf;
104                 }
105                 xmax=max(xmax,x+t);
106                 ymax=max(ymax,y);
107             }
108             else
109             {
110                 for(j=0; j<t; j++)
111                 {
112                     l[x][y+j]=inf;
113                 }
114                 xmax=max(xmax,x);
115                 ymax=max(ymax,y+t);
116             }
117         }
118         for(i=0; i<m; i++)
119         {
120             scanf("%d%d%d",&x,&y,&d);
121             if(d==0)
122             {
123                 h[x][y]=1;
124             }
125             else l[x][y]=1;
126         }
127         scanf("%lf%lf",&tx,&ty);
128         if(tx>xmax||ty>ymax)
129         {
130             printf("0
");
131         }
132         else
133         {
134             sx=(int)tx;
135             sy=(int)ty;
136             bfs();
137             printf("%d
",dis[sx][sy]);
138         }
139     }
140 }