poj2049Finding Nemo（BFS+优先队列）

http://poj.org/problem?id=2049

与一般的BFS不大一样是把网格转换成我们常用的点

以左下角的点表示整个方格用优先队列来保证每次搜的都是最小的注意Nemo的位置有可能不在墙内

之前把sx看成tx一直调试不出来，，纠结了一天第二天一眼看出它俩不一样。。改完之后找了找结构体的优先队列怎么用按知道上回答写的一直WA 后来看人家的解题报告发现不是那么用的，改过来交上AC。。

View Code

  1 #include<stdio.h>
  2 #include<string.h>
  3 #include<iostream>
  4 #include<queue>
  5 using namespace std;
  6 typedef struct node
  7 {
  8     int num,x,y;
  9     friend bool operator<( struct node a, struct node b )
 10     {
 11         return a.num>b.num;
 12     }
 13 }st;
 14 int p[2][301][301],pt[2][300][300],pf[300][300];
 15 st ne,na;
 16 int main()
 17 {
 18  int n,m,i,j,x,y,t,d,g;
 19  float x1,y1;
 20  while(cin>>n>>m)
 21  {
 22      if(n==-1&&m==-1)
 23      break;
 24   memset(p,0,sizeof(p));
 25   memset(pf,0,sizeof(pf));
 26   memset(pt,0,sizeof(pt));
 27   int f = 1;
 28   int minx=300,miny = 300,maxx = -1,maxy = -1;
 29   for(i = 1; i <= n ; i++)
 30   {
 31    cin>>x>>y>>t>>d;
 32    if(x<minx)
 33     minx = x;
 34    if(y<miny)
 35     miny = y;
 36    if(t==0)
 37    {
 38     if(maxx<x+d)
 39      maxx = x+d;
 40      if(maxy<y)
 41      maxy = y;
 42     for(g = x ; g < x+d ; g++)
 43      p[0][g][y] = 1;
 44    }
 45    else
 46    {
 47     if(maxy<y+d)
 48      maxy = y+d;
 49     if(maxx<x)
 50      maxx = x;
 51     for(g = y ;g < y+d ; g++)
 52      p[1][x][g] = 1;
 53    }
 54   }
 55   for(i = 1; i <= m ; i++)
 56   {
 57    cin>>x>>y>>t;
 58    if(maxx<x)
 59      maxx = x;
 60     if(maxy<y)
 61      maxy = y;
 62      if(minx>x)
 63      minx = x;
 64      if(miny>y)
 65      miny = y;
 66    pt[t][x][y] = 1;
 67   }
 68   scanf("%f%f", &x1,&y1);
 69   int sx = (int)x1;
 70   int sy = (int)y1;
 71   int flag = 0;
 72   if(sx>maxx||sx<minx||sy>maxy||sy<miny)
 73   f = 0;
 74   else
 75   {
 76       priority_queue <st> q;
 77       ne.num = 0;
 78       ne.x = sx;
 79       ne.y = sy;
 80       q.push(ne);
 81       pf[sx][sy]=1;
 82       while(!q.empty())
 83       {
 84           na = q.top();
 85           int tx = na.x;
 86           int ty = na.y;
 87           q.pop();
 88           if(tx>=maxx||tx<minx||ty>=maxy||ty<miny)
 89           {
 90               flag = 1;
 91               break;
 92           }
 93           if((pt[1][tx][ty]||!p[1][tx][ty])&&tx-1>=0&&!pf[tx-1][ty])
 94             {
 95                 pf[tx-1][ty] = 1;
 96                 if(pt[1][tx][ty])
 97                 ne.num = na.num+1;
 98                 else
 99                 ne.num = na.num;
100                 ne.x = tx-1;
101                 ne.y = ty;
102                 q.push(ne);
103             }
104             if((pt[1][tx+1][ty]||!p[1][tx+1][ty])&&!pf[tx+1][ty])
105             {
106                 pf[tx+1][ty] = 1;
107                 if(pt[1][tx+1][ty])
108                 ne.num = na.num+1;
109                 else
110                 ne.num = na.num ;
111                 ne.x = tx+1;
112                 ne.y = ty;
113                 q.push(ne);
114             }
115             if((pt[0][tx][ty+1]||!p[0][tx][ty+1])&&!pf[tx][ty+1])
116             {
117                 pf[tx][ty+1] = 1;
118                 if(pt[0][tx][ty+1])
119                 ne.num = na.num+1;
120                 else
121                 ne.num = na.num;
122                 ne.x = tx;
123                 ne.y = ty+1;
124                 q.push(ne);
125             }
126             if((pt[0][tx][ty]||!p[0][tx][ty])&&ty-1>=0&&!pf[tx][ty-1])
127             {
128                 pf[tx][ty-1] = 1;
129                 if(pt[0][tx][ty])
130                 ne.num = na.num+1;
131                 else
132                 ne.num = na.num ;
133                 ne.x = tx;
134                 ne.y = ty-1;
135                 q.push(ne);
136             }
137       }
138   }
139   if(!f||!flag)
140   {
141       if(!f)
142       cout<<"0"<<endl;
143       else
144       cout<<"-1"<<endl;
145   }
146   else
147       cout<<na.num<<endl;
148  }
149  return 0;
150 }