题意:
网格图上有N个敌人的据点。求从起点到终点路径中到敌人据点Manhattan distance: dist((
x1,
y1), (
x2,
y2)) = |
x2 −
x1| + |
y2 −
y1|. 最长距离,如果有重复,则使得路径长度最短。
解法:
二分路径中到敌人据点的最短距离,然后用BFS check
注意在chk时可以开个bool数组来标记,不用标记到所有的不合法点,只要标记其轮廓就可以了,这样可以降低复杂度的阶
代码:
1
# include <cstdio>
2
# include <cstring>
3
using namespace std;
4
int n,w,h,sx,sy,ex,ey;
5
int p[10001][2];
6
int q[1000005][2];
7
int map[1001][1001];
8
# define abs(a) ((a)>0?(a):-(a))
9
# define legal(a,b) ((a)>=0&&(a)<w&&(b)>=0&&(b)<h)
10
int chk(int limit)
11

{
12
memset(map,-1,sizeof(map));
13
for(int i=0;i<n;i++)
14
for(int l=0;l<=limit;l++)
15
{
16
if(legal(p[i][0]-l,p[i][1]+limit-l))
17
map[p[i][0]-l][p[i][1]+limit-l]=-2;
18
if(legal(p[i][0]+l,p[i][1]+limit-l))
19
map[p[i][0]+l][p[i][1]+limit-l]=-2;
20
if(legal(p[i][0]-l,p[i][1]-limit+l))
21
map[p[i][0]-l][p[i][1]-limit+l]=-2;
22
if(legal(p[i][0]+l,p[i][1]-limit+l))
23
map[p[i][0]+l][p[i][1]-limit+l]=-2;
24
}
25
for(int i=0;i<n;i++)
26
if(abs(p[i][0]-sx)+abs(p[i][1]-sy)<=limit||abs(p[i][0]-ex)+abs(p[i][1]-ey)<=limit) return -1;
27
int s=-1,e=-1;
28
e++;
29
q[e][0]=sx;
30
q[e][1]=sy;
31
map[sx][sy]=0;
32
while(s!=e)
33
{
34
s++;
35
int x=q[s][0],y=q[s][1];
36
if(legal(x-1,y)&&map[x-1][y]==-1)
37
{
38
e++;
39
q[e][0]=x-1;
40
q[e][1]=y;
41
map[q[e][0]][q[e][1]]=map[x][y]+1;
42
}
43
if(legal(x+1,y)&&map[x+1][y]==-1)
44
{
45
e++;
46
q[e][0]=x+1;
47
q[e][1]=y;
48
map[q[e][0]][q[e][1]]=map[x][y]+1;
49
}
50
if(legal(x,y-1)&&map[x][y-1]==-1)
51
{
52
e++;
53
q[e][0]=x;
54
q[e][1]=y-1;
55
map[q[e][0]][q[e][1]]=map[x][y]+1;
56
}
57
if(legal(x,y+1)&&map[x][y+1]==-1)
58
{
59
e++;
60
q[e][0]=x;
61
q[e][1]=y+1;
62
map[q[e][0]][q[e][1]]=map[x][y]+1;
63
}
64
}
65
return map[ex][ey]==-2||map[ex][ey]==-1?-1:map[ex][ey];
66
}
67
int main()
68

{
69
int test;
70
scanf("%d",&test);
71
while(test--)
72
{
73
scanf("%d%d%d%d%d%d%d",&n,&w,&h,&sx,&sy,&ex,&ey);
74
for(int i=0;i<n;i++)
75
scanf("%d%d",&p[i][0],&p[i][1]);
76
int s=0,e=(w>h?w:h)-1;
77
while(s<=e)
78
{
79
int mid=(s+e)>>1;
80
if(chk(mid)!=-1) s=mid+1;
81
else e=mid-1;
82
}
83
printf("%d %d\n",e+1,chk(e));
84
}
85
return 0;
86
}
87