NOIP 模拟赛 23 T4 大逃亡O(二分+广搜)(∩_∩)O

2 5 6
0 0 4 0
2 1
2 3

2 14



考试总结：

• 这题感觉还比较简单（相对于考试的其他题目来说），对于其他的什么折半搜索，dp，瞎搞，这题就属于只要你想写，码力还可以基本上都可以写出来
• 这题的题目里明确说了要是最小值最大，所以这题很明显就是二分
• 二分什么呢，看完题目就可以得知只能是离最近的敌人的距离。
• 先预处理一下所有点到自己最近敌人的距离，然后去二分，再原来的图上跑暴力搜索，然后就没了，真的没了
• 搞不懂为什么这题没人打呢，传说中的有分不要？
• 放下代码

   1 #include<cstdio>
   2 #include<iostream>
   3 #include<cstring>
   4 #include<queue>
   5 using namespace std;
   6 const int maxn=1010;
   7 const int mx[]={1,-1,0,0};
   8 const int my[]={0,0,1,-1};
   9 int n,m,dis[maxn][maxn],tim[maxn][maxn],vis[maxn][maxn];
  10 queue< int > q;
  11 void caltime() //预处理出所有点到最近敌人的距离 
  12 {
  13     while(!q.empty()) 
  14     {
  15         int x=q.front()/m;
  16         int y=q.front()%m;
  17         q.pop();
  18         for(int dir=0;dir<=3;dir++)
  19         {
  20             int nx=x+mx[dir];
  21             int ny=y+my[dir];
  22             if(nx>=0&&nx<n&&ny>=0&&ny<m&&!vis[nx][ny]) 
  23             {
  24                 vis[nx][ny]=1;
  25                 tim[nx][ny]=tim[x][y]+1;
  26                 q.push(nx*m+ny);
  27             }
  28         }
  29     }
  30     memset(vis,0,sizeof(vis));
  31 }
  32 int check(int mid,int x1,int x2,int y1,int y2) //开始爆搜，怎么暴力怎么来 
  33 {
  34     if(tim[x1][y1]<mid)
  35     {
  36         return 0;       
  37     }
  38     memset(vis,0,sizeof(vis));
  39     q.push(x1*m+y1);
  40     vis[x1][y1]=1;
  41     dis[x1][y1]=0;
  42     while(!q.empty()) 
  43     {
  44         int x=q.front()/m;
  45         int y=q.front()%m;
  46         q.pop();
  47         for(int dir=0;dir<=3;dir++)
  48         {
  49             int nx=x+mx[dir];
  50             int ny=y+my[dir];
  51             if(nx>=0&&nx<n&&ny>=0&&ny<m&&!vis[nx][ny]&&tim[nx][ny]>=mid) 
  52             {
  53                 vis[nx][ny]=1;
  54                 dis[nx][ny]=dis[x][y]+1;
  55                 q.push(nx*m+ny);
  56             }
  57         }
  58     }
  59     return vis[x2][y2];
  60 }
  61 int main() 
  62 {
  63     ios::sync_with_stdio(false);
  64     int c;
  65     cin>>c;
  66     cin>>n>>m;
  67     int x1,y1,x2,y2;
  68     cin>>x1>>y1>>x2>>y2;
  69     for(int i=1;i<=c;i++) 
  70     {
  71         int x,y;
  72         cin>>x>>y;
  73         tim[x][y]=0;
  74         vis[x][y]=1;
  75         q.push(x*m+y);
  76     }
  77     caltime();
  78     int l=0,r=max(n,m)+1,mid;
  79     while(l+1<r) //二分能当答案的距离 
  80     {
  81         if(check(mid=l+r>>1,x1,x2,y1,y2)) 
  82         {
  83             l=mid;
  84         }
  85         else
  86         {
  87             r=mid;
  88         } 
  89     }
  90     check(l,x1,x2,y1,y2);
  91     cout<<l<<" "<<dis[x2][y2]<<endl;
  92     return 0;
  93 }

   

总结一下：

　　考试时要懂得放弃，不要死搞一题，，对于一些暴力可以过得东西要去打