Description
给出数字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|
行号从0到X-1,列号从0到Y-1再给出四个数字x1,y1,x2,y2,代表你要从点(x1,y1)移到(x2,y2)。在移动的过程中你
当然希望离敌人的距离的最小值最大化，现在请求出这个值最大可以为多少,以及在这个前提下你最少要走多少步
才可以回到目标点。注意这里距离的定义为两点的曼哈顿距离，即某两个点的坐标分为(a,b),(c,d)那么它们的距
离为|a-c|+|b-d|
Input
第一行给出数字N，X，Y
第二行给出x1,y1,x2,y2
下面将有N行，给出N个敌人所在的坐标
第二行给出x1,y1,x2,y2
下面将有N行，给出N个敌人所在的坐标
Output
在一行内输出你离敌人的距离及在这个距离的限制下，你回到目标点最少要移动多少步。
Sample Input
2 5 6
0 0 4 0
2 1
2 3
Sample Output
2 14
/*
①灌水法 by hzwer
②二维前缀和 by me
③并查集乱搞 by 某神犇
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<map>
#include<vector>
#define ll long long
#define x1 X1
#define y1 Y1
#define x2 X2
#define y2 Y2
using namespace std;
inline int read()
{
int x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
int ans1,ans2;
int head,tail;
int n,X,Y;
int x1,y1,x2,y2;
int mp[][];
int x[],y[],step[];
bool vis[][];
int xx[]={,-,,},yy[]={,,,-};
void pre()
{
while(head!=tail)
{
int nx=x[head],ny=y[head];head++;
for(int k=;k<;k++)
{
int tx=nx+xx[k],ty=ny+yy[k];
if(tx>=X||ty>=Y||tx<||ty<||mp[tx][ty]!=-)continue;
mp[tx][ty]=mp[nx][ny]+;
x[tail]=tx;y[tail]=ty;tail++;
}
}
}
int bfs(int val)
{
head=;tail=;
if(x1==x2&&y1==y2)return ;
memset(vis,,sizeof(vis));
vis[x1][y1]=;x[]=x1;y[]=y1;
while(head!=tail)
{
int nx=x[head],ny=y[head],ns=step[head];head++;
for(int k=;k<;k++)
{
int tx=nx+xx[k],ty=ny+yy[k];
if(tx>=X||ty>=Y||tx<||ty<||mp[tx][ty]<val||vis[tx][ty])continue;
vis[tx][ty]=;
if(tx==x2&&ty==y2)return ns+;
x[tail]=tx;y[tail]=ty;step[tail]=ns+;tail++;
}
}
return -;
}
int main()
{
//freopen("escape.in","r",stdin);
//freopen("escape.out","w",stdout);
memset(mp,-,sizeof(mp));
n=read();X=read();Y=read();
x1=read();y1=read();x2=read();y2=read();
for(int i=;i<=n;i++)
{
int a=read(),b=read();
mp[a][b]=;
x[tail]=a;y[tail]=b;tail++;
}
pre();
int l=,r=mp[x1][y1];
while(l<=r)
{
int mid=(l+r)>>;
int t=bfs(mid);
if(t==-)r=mid-;
else l=mid+,ans1=mid,ans2=t;
}
printf("%d %d\n",ans1,ans2);
return ;
} #include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
using namespace std;
const int maxn = ,inf = ;
inline int read(){
char ch=getchar();
int f=,x=;
while(!(ch>=''&&ch<='')){if(ch=='-')f=-;ch=getchar();};
while(ch>=''&&ch<=''){x=x*+(ch-'');ch=getchar();};
return x*f;
}
struct nd{
int x;
int y;
};
int p,n,m;
int ex[maxn],ey[maxn],xa,xb,ya,yb;
int flag,dis[][],vis[][];
short d[][],s[][];
int dx[] = {,,-,};
int dy[] = {,,,-};
bool emy[][];
inline bool jud(int x,int y,int t){
if(x < || y < || x >= m || y >= n) return false;
if(t == ) return true;
t--;
int tx=+x-y+t,ty=x+y+t,dx=+x-y-t,dy=x+y-t;
if(ty>=n+m-) ty = n+m-;
if(tx>=+m) tx = +m;
int tot = s[ty][tx];
if(dy>&&dx>-n) tot += s[dy-][dx-];
if(dy>) tot -= s[dy-][tx];
if(dx>-n) tot -= s[ty][dx-];
if(tot) return false;
else return true;
}
bool check(int t){
if(!jud(xa,ya,t)) return false;
flag++;
for(int i = ;i <= n+;i++){
for(int j = ;j <= m+;j++){
dis[i][j] = inf;
}
}
nd now,nxt;
now.x = xa;
now.y = ya;
queue<nd> q;
q.push(now);
dis[ya][xa] = ;
vis[ya][xa] = flag;
while(!q.empty()){
now = q.front();
q.pop();
//cout<<now.y<<" "<<now.x<<endl;
for(int dr = ;dr < ;dr++){
nxt.x = now.x + dx[dr];
nxt.y = now.y + dy[dr];
if(jud(nxt.x,nxt.y,t)&&vis[nxt.y][nxt.x] != flag){
dis[nxt.y][nxt.x] = dis[now.y][now.x] + ;
vis[nxt.y][nxt.x] = flag;
q.push(nxt);
if(nxt.y == yb && nxt.x == xb) return true;
}
}
}
return false;
}
int main(){
cin>>p>>m>>n>>xa>>ya>>xb>>yb;
for(int i = ;i <= p;i++){
scanf("%d%d",&ex[i],&ey[i]);
emy[ex[i]+ey[i]][+ex[i]-ey[i]] = true;
}
for(int i = ;i < n + m - ;i++){
for(int j = -n;j < +m;j++){
if(emy[i][j]) d[i][j] = d[i][j-] + ;
else d[i][j] = d[i][j-];
}
}
for(int i = ;i < n + m - ;i++){
for(int j = -n;j < +m;j++){
if(!i) s[i][j] = d[i][j];
else s[i][j] = s[i-][j] + d[i][j];
}
}
int l = ,r = n + m,mid,ans1,ans2;
while(l <= r){
mid = (l + r) >> ;
if(check(mid)){
ans1 = mid;
ans2 = dis[yb][xb];
l = mid + ;
}else{
r = mid - ;
}
}
cout<<ans1<<" "<<ans2;
return ;
} #include <cstdio>
#include <queue>
#include <cstring>
using namespace std; const int N=+;
const int X=+, Y=+;
const int pace[][]={{, }, {, }, {, -}, {-, }}; int n, sz_x, sz_y; struct Point {
int x, y;
inline Point(int _x=, int _y=): x(_x), y(_y) {}
inline Point walk(int k) {
return Point(x+pace[k][], y+pace[k][]);
}
}; Point S, D; int dis_enemy[X][Y]; inline void read_general() {
scanf("%d%d%d", &n, &sz_x, &sz_y);
scanf("%d%d%d%d", &S.x, &S.y, &D.x, &D.y);
} inline void read_enemy_and_process_dis() {
memset(dis_enemy, 0x3f, sizeof(dis_enemy));
queue<Point> q;
for(int i=; i<=n; ++i) {
Point E; scanf("%d%d", &E.x, &E.y);
dis_enemy[E.x][E.y]=;
q.push(E);
}
while(!q.empty()) {
Point U=q.front(); q.pop();
for(int k=; k<; ++k) {
Point V=U.walk(k);
if(V.x< || V.x>=sz_x || V.y< || V.y>=sz_y ||
dis_enemy[V.x][V.y]<0x3f3f3f00) continue;
dis_enemy[V.x][V.y]=dis_enemy[U.x][U.y]+;
q.push(V);
}
}
} int dis_s[X][Y]; inline int calc_dist(int mid) {
memset(dis_s, 0x3f, sizeof(dis_s));
queue<Point> q;
if(dis_enemy[S.x][S.y]>=mid) {
q.push(S);
dis_s[S.x][S.y]=;
}
while(!q.empty()) {
Point U=q.front(); q.pop();
for(int k=; k<; ++k) {
Point V=U.walk(k);
if(V.x< || V.x>=sz_x || V.y< || V.y>=sz_y ||
dis_enemy[V.x][V.y]<mid ||
dis_s[V.x][V.y]<0x3f3f3f00) continue;
dis_s[V.x][V.y]=dis_s[U.x][U.y]+;
q.push(V);
}
}
return dis_s[D.x][D.y];
} int main() {
read_general();
read_enemy_and_process_dis();
int l=, r=;
while(l<r-) {
int mid=(l+r)>>;
if(calc_dist(mid)<0x3f3f3f00) l=mid; else r=mid;
}
printf("%d %d\n", l, calc_dist(l));
return ;
}