hdu2337 Escape From Enemy Territory---二分bfs+预处理 - c++编程基础

题意：

地图中有一些点危险，要从起点走到终点，且离危险点最近的距离最大，求出此时的最短路径。

思路：

bfs，重点是如何处理要使离危险点的距离最大，直观的想法是对离危险点的距离的所有可能从小到大都尝试下，能求得通路的解里面，离危险点距离最大的情况就是正确解。

因此，可以对地图上每个点到危险点的距离预处理一下。

在尝试通路的过程中，可以用二分的方法来取这个离危险点的距离，感觉很好啊。

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
           #define inf 0x3f3f3f3f using namespace std; struct node { int x,y,t; }tmp,now; int dx[]={0,0,-1,1}; int dy[]={-1,1,0,0}; int mp[1005][1005],vis[1005][1005],n,X,Y,sx,sy,ex,ey,bot,mid,top,ans,maxd; queue
           
             q; int ok(int a,int b) { if(a>=0&&a
            
             =0&&b
             
              maxd) maxd=now.t; q.push(now); } } } int bfs(int num) { memset(vis,0,sizeof vis); while(!q.empty()) q.pop(); int i; tmp.x=sx; tmp.y=sy; tmp.t=0; vis[sx][sy]=1; q.push(tmp); while(!q.empty()) { tmp=q.front(); q.pop(); for(i=0;i<4;i++) { now.x=tmp.x+dx[i]; now.y=tmp.y+dy[i]; now.t=tmp.t+1; if(!ok(now.x,now.y)||mp[now.x][now.y]
              
               >1; if(mp[sx][sy]