给一个起点一个终点， 给出整个地图的宽和高， 给出n个敌人的坐标。 让你找到一条路径， 这条路径上的点距离所有敌人的距离都最短， 输出最短距离。
首先预处理出来地图上的所有点到敌人的最短距离， 然后二分距离， bfs就可以。
tle了好多次， 到网上搜题解， 看到别人是先把敌人的坐标都存到数组里最后在一起预处理， 而我是读一个点处理一个点， 改了以后才ac.......
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define pb(x) push_back(x) 4 #define ll long long 5 #define mk(x, y) make_pair(x, y) 6 #define mem(a) memset(a, 0, sizeof(a)) 7 #define lson l, m, rt<<1 8 #define rson m+1, r, rt<<1|1 9 #define mem1(a) memset(a, -1, sizeof(a)) 10 #define mem2(a) memset(a, 0x3f, sizeof(a)) 11 #define rep(i, a, n) for(int i = a; i<n; i++) 12 #define ull unsigned long long 13 typedef pair<int, int> pll; 14 const double PI = acos(-1.0); 15 const int inf = 1061109567; 16 const double eps = 1e-8; 17 const int mod = 1e9+7; 18 const int dir[][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} }; 19 int dis[1005][1005], x, y, n, x1, y1, x2, y2, vis[1005][1005]; 20 pll point[10005]; 21 struct node 22 { 23 int x, y, step; 24 node(){} 25 node(int x, int y, int step):x(x),y(y),step(step){} 26 }; 27 28 void bfs() { 29 queue <node> q; 30 for(int i = 0; i<n; i++) { 31 q.push(node(point[i].first, point[i].second, 0)); 32 dis[point[i].first][point[i].second] = 0; 33 } 34 while(!q.empty()) { 35 node tmp = q.front(); q.pop(); 36 for(int i = 0; i<4; i++) { 37 int tmpx = tmp.x+dir[i][0]; 38 int tmpy = tmp.y+dir[i][1]; 39 if(tmpx>=0&&tmpx<x&&tmpy>=0&&tmpy<y) { 40 if(dis[tmpx][tmpy]>tmp.step+1) { //这里要注意 41 dis[tmpx][tmpy] = tmp.step+1; 42 q.push(node(tmpx, tmpy, tmp.step+1)); 43 } 44 } 45 } 46 } 47 } 48 49 int bin(int val) { 50 if(dis[x1][y1]<val) 51 return 0; 52 queue <node> q; 53 mem(vis); 54 q.push(node(x1, y1, 0)); 55 vis[x1][y1] = 1; 56 while(!q.empty()) { 57 node tmp = q.front(); q.pop(); 58 if(tmp.x == x2 && tmp.y == y2) 59 return tmp.step; 60 for(int i = 0; i<4; i++) { 61 int tmpx = tmp.x+dir[i][0]; 62 int tmpy = tmp.y + dir[i][1]; 63 if(tmpx>=0&&tmpx<x&&tmpy>=0&&tmpy<y&&!vis[tmpx][tmpy]) { 64 vis[tmpx][tmpy] = 1; 65 if(dis[tmpx][tmpy]>=val) { 66 q.push(node(tmpx, tmpy, tmp.step+1)); 67 } 68 } 69 } 70 } 71 return 0; 72 } 73 74 int main() 75 { 76 int t, a, b; 77 cin>>t; 78 while(t--) { 79 mem2(dis); 80 scanf("%d%d%d", &n, &x, &y); 81 scanf("%d%d%d%d", &x1, &y1, &x2, &y2); 82 for(int i = 0; i<n; i++) { 83 scanf("%d%d", &a, &b); 84 point[i] = mk(a, b); 85 } 86 bfs(); 87 int l = 0, r = dis[x1][y1], ans, ans1, ans2; 88 while(l<=r) { 89 int m = l+r>>1; 90 ans = bin(m); 91 if(ans>0) { 92 l = m+1; 93 ans1 = m; 94 ans2 = ans; 95 } else { 96 r = m-1; 97 } 98 } 99 printf("%d %d ", r, ans2); 100 } 101 }