hdu 2337 Escape from Enemy Territory

题目大意

给你一张nn*mm矩形地图。上面有些点上有敌营。给你起点和终点, 你找出一条最优路径。满足最优路径上的点离敌营的最近最短距离是所有路径最短的。若有多条找路径最短的一条。

分析

通过二分来确定路径离敌营最短距离。然后bfs来验证。

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<iostream>
  4 #include<algorithm>
  5 #include<cmath>
  6 #include<string>
  7 #include<queue>
  8 #include<stack>
  9 #include<map>
 10 #include<vector>
 11 #define maxn 1010
 12 #define MAXN 2005
 13 #define MAXM 20000005
 14 #define INF  100000000000000
 15 #define oo 1000000007
 16 using namespace  std;
 17 
 18 typedef long long LL;
 19 struct Point
 20 {
 21     int x,y,dist;
 22 }p[maxn*maxn];
 23 int mid,n,nn,mm,stx,sty,edx,edy;
 24 int vist[maxn][maxn],vistdist[maxn][maxn];
 25 int dirx[]={0,-1,0,1};
 26 int diry[]={-1,0,1,0};
 27 int max_dist,dist1,dist2;
 28 void bfs1()
 29 {
 30     queue<Point> q;
 31     while(!q.empty())
 32         q.pop();
 33     for(int i=0;i<n;i++)
 34         q.push(p[i]);
 35     while(!q.empty())
 36     {
 37         Point tem=q.front();
 38         q.pop();
 39 
 40         for(int i=0;i<4;i++)
 41         {
 42            int newx=tem.x+dirx[i];
 43            int newy=tem.y+diry[i];
 44            if(newx>=0&&newx<mm&&newy>=0&&newy<nn&&!vist[newx][newy])
 45            {
 46                vist[newx][newy]=1;
 47                int newdist=tem.dist+1;
 48                vistdist[newx][newy]=newdist;
 49                max_dist=max(max_dist,newdist);
 50                Point pp;
 51                pp.x=newx;
 52                pp.y=newy;
 53                pp.dist=newdist;
 54                q.push(pp);
 55            }
 56         }
 57     }
 58 }
 59 int bfs2()
 60 {
 61     queue<Point> q;
 62     while(!q.empty())
 63         q.pop();
 64     Point pp;
 65     pp.x=stx;
 66     pp.y=sty;
 67     pp.dist=0;
 68     q.push(pp);
 69     memset(vist,0,sizeof(vist));
 70     if(vistdist[stx][sty]<mid)
 71         return 0;
 72 
 73     while(!q.empty())
 74     {
 75         Point tem=q.front();
 76         q.pop();
 77         if(tem.x==edx&&tem.y==edy)
 78         {
 79             dist1=mid;
 80             dist2=tem.dist;
 81             return 1;
 82         }
 83         for(int i=0;i<4;i++)
 84         {
 85             int xx=tem.x+dirx[i];
 86             int yy=tem.y+diry[i];
 87             if(xx>=0&&xx<mm&&yy>=0&&yy<nn&&!vist[xx][yy]&&vistdist[xx][yy]>=mid)
 88             {
 89                 vist[xx][yy]=1;
 90                 Point pp;
 91                 pp.x=xx;
 92                 pp.y=yy;
 93                 pp.dist=tem.dist+1;
 94                 q.push(pp);
 95             }
 96 
 97         }
 98     }
 99     return 0;
100 
101 }
102 int main()
103 {
104     int t;
105     scanf("%d",&t);
106     while(t--)
107     {
108         scanf("%d %d %d",&n,&mm,&nn);
109         scanf("%d %d %d %d",&stx,&sty,&edx,&edy);
110         memset(vist,0,sizeof(vist));
111         for(int i=0;i<n;i++)
112         {
113             scanf("%d %d",&p[i].x,&p[i].y);
114             p[i].dist=0;
115             vistdist[p[i].x][p[i].y]=0;
116             vist[p[i].x][p[i].y]=1;
117         }
118         max_dist=-1;
119         bfs1();
120         int l=0,r=max_dist;
121         while(l<=r)
122         {
123             mid=(l+r)/2;
124             if(bfs2())
125                l=mid+1;
126             else
127                 r=mid-1;
128 
129         }
130         printf("%d %d
",dist1,dist2);
131     }
132     return 0;
133 }

注意的是队列数组别开小了，还有就是插入队列的时候应该这样写

     Point pp;
               pp.x=newx;
               pp.y=newy;
               pp.dist=newdist;
               q.push(pp);

如果这样写就会CE

 q.push((Point){newx,newy,newdist});