題意：
網(wǎng)格圖上有N個敵人的據(jù)點(diǎn)。求從起點(diǎn)到終點(diǎn)路徑中到敵人據(jù)點(diǎn)Manhattan distance: dist((
x1,
y1), (
x2,
y2)) = |
x2 −
x1| + |
y2 −
y1|. 最長距離，如果有重復(fù)，則使得路徑長度最短。
解法：
二分路徑中到敵人據(jù)點(diǎn)的最短距離，然后用BFS check
注意在chk時可以開個bool數(shù)組來標(biāo)記，不用標(biāo)記到所有的不合法點(diǎn)，只要標(biāo)記其輪廓就可以了，這樣可以降低復(fù)雜度的階
代碼：
1
# include <cstdio>
2# include <cstring>
3using namespace std;
4int n,w,h,sx,sy,ex,ey;
5int p[10001][2];
6int q[1000005][2];
7int map[1001][1001];
8# define abs(a) ((a)>0?(a):-(a))
9# define legal(a,b) ((a)>=0&&(a)<w&&(b)>=0&&(b)<h)
10int 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
}
67int 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