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

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

题目描述

给出数字N(1≤N≤10000),X(1≤x≤1000),Y(1≤Y≤1000),代表有N个敌人分布一个X行Y列的矩阵上,矩形的行号从0到X-1,列号从0到Y-1再给出四个数字x1,y1,x2,y2,代表你要从点(x1,y1)移到(x2,y2)。
在移动的过程中你当然希望离敌人的距离的最小值最大化,现在请求出这个值最大可以为多少,以及在这个前提下,你最少要走多少步才可以回到目标点。
注意这里距离的定义为两点的曼哈顿距离,即某两个点的坐标分为(a,b),(c,d),那么它们的距离为|a-c|+|b-d|。
注意:C++11里，不能定义变量名为Y1或者y1。

输入

第1行:给出数字N,X,Y;
第2行:给出 x1,y1,x2,y2;
接下来N行:给出N个敌人所在的坐标.
1≤N≤10000,1≤x≤1000,1≤Y≤1000.

输出

输出2个数:你离敌人的距离及在这个距离的限制下,你回到目标点最少要移动多少步.

样例输入 Copy

样例输出 Copy

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 }

总结一下：

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