CF Gym101173H Hangar Hurdles

发表于 | 分类于

Description

给你一个\(n\times n\)的网格，每个点要么是空地要么是障碍。

然后进行\(q\)次询问，每次询问就是要求你在一个格子\((x, y)\)处安排一个以格子\((x, y)\)的中心为中心的边长尽可能长的格点正方形，然后上下左右移动（每次移动一格）使其中心落在另一格子\((u, v)\)处，注意整个过程中不能撞到障碍格子内部。

\(2\leq n\leq 1000, 1\leq q\leq 3\times 10^5\)。

Solution

先考虑求在格子\((x, y)\)最大能放多大的正方形吧。

要求不能碰到障碍，换言之若对于任意障碍\((u, v)\)，正方形边长若大于\(\max(|u - x|, |y - v|)\)就会出事（不就是切比雪夫距离吗）。因此我们要对所有的这种值取个最小，这很容易用多源BFS完成……

再往下就处理一下边权，然后就相当于询问瓶颈路了……因此求下最小瓶颈生成树，倍增回答即可。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
#include <cstdio>
#include <cstring>
#include <cstring>
#include <algorithm>
#include <functional>
#include <utility>
#include <vector>
#include <queue>
const int maxn = 1005;
int dis[maxn][maxn]; int n;
using pii = std::pair<int, int>;
inline void relax(int x, int y, int a, int b, std::queue<pii> &Q) {
  if(a == 0 || a > n || b == 0 || b > n) return;
  if(dis[x][y] + 1 < dis[a][b]) {
    dis[a][b] = dis[x][y] + 1;
    Q.push({a, b});
  }
}
void bfs() {
  std::queue<pii> Q;
  for(int i = 1; i <= n; i ++) {
    for(int j = 1; j <= n; j ++) {
      if(!dis[i][j]) Q.push({i, j});
    }
  }
  while(!Q.empty()) {
    pii u = Q.front(); Q.pop();
    int x = u.first, y = u.second;
    relax(x, y, x - 1, y, Q);
    relax(x, y, x, y - 1, Q);
    relax(x, y, x - 1, y - 1, Q);
    relax(x, y, x + 1, y, Q);
    relax(x, y, x, y + 1, Q);
    relax(x, y, x + 1, y + 1, Q);
    relax(x, y, x + 1, y - 1, Q);
    relax(x, y, x - 1, y + 1, Q);
  }
  for(int i = 1; i <= n; i ++) {
    for(int j = 1; j <= n; j ++) {
      if(dis[i][j]) dis[i][j] = 2 * dis[i][j] - 1;
    }
  }
}

const int maxno = 1000005;
int id(int x, int y) {
  return (x - 1) * n + y;
}

struct Edge {
  int u, v, d;
  Edge(int a = 0, int b = 0, int c = 0) {
    u = a; v = b; d = c;
  }
  bool operator <(const Edge &res) const {
    return d < res.d;
  }
  bool operator >(const Edge &res) const {
    return d > res.d;
  }
};
std::vector<Edge> G[maxno];
void add_edge(int u, int v, int d) {
  G[u].push_back(Edge(u, v, d));
}
void ins_edge(int u, int v, int d) {
  add_edge(u, v, d); add_edge(v, u, d);
}

int p[maxno], rk[maxno];
void init_set() {
  for(int i = 1; i <= n * n; i ++) {
    p[i] = i; rk[i] = 0;
  }
}
int get_fa(int x) {
  if(x == p[x]) return x;
  else return (p[x] = get_fa(p[x]));
}
void link_set(int x, int y) {
  if(rk[x] > rk[y]) std::swap(x, y);
  p[x] = y;
  if(rk[x] == rk[y]) rk[y] ++;
}
void merge_set(int x, int y) {
  link_set(get_fa(x), get_fa(y));
}
bool is_same(int x, int y) {
  return (get_fa(x) == get_fa(y));
}

void gen_tree() {
  init_set();
  std::vector<Edge> E;
  for(int i = 1; i <= n; i ++) {
    for(int j = 1; j <= n; j ++) {
      int u = id(i, j);
      if(i < n) {
        E.push_back(Edge(u, id(i + 1, j), std::min(dis[i][j], dis[i + 1][j])));
      }
      if(j < n) {
        E.push_back(Edge{u, id(i, j + 1), std::min(dis[i][j], dis[i][j + 1])});
      }
    }
  }
  std::sort(E.begin(), E.end(), std::greater<Edge>());
  for(const Edge &e : E) {
    int x = e.u, y = e.v, d = e.d;
    if(!is_same(x, y)) {
      merge_set(x, y);
      ins_edge(x, y, d);
    }
  }
}
int anc[maxno][20], cost[maxno][20], dep[maxno];
void dfs(int x, int depth = 0, int fa = -1) {
  anc[x][0] = fa; dep[x] = depth;
  for(const Edge &e : G[x]) {
    int v = e.v, d = e.d;
    if(v != fa) {
      cost[v][0] = d;
      dfs(v, depth + 1, x);
    }
  }
}
void process() {
  memset(anc, -1, sizeof(anc));
  bfs(); gen_tree(); dfs(1);
  for(int j = 1; (1 << j) < (n * n); j ++) {
    for(int i = 1; i <= (n * n); i ++) {
      int a = anc[i][j - 1];
      if(a != -1) {
        anc[i][j] = anc[a][j - 1];
        cost[i][j] = std::min(cost[i][j - 1], cost[a][j - 1]);
      }
    }
  }
}
int query(int x, int y) {
  if(dep[x] < dep[y]) std::swap(x, y);
  int ans = 0x7f7f7f7f;
  for(int j = 19; j >= 0; j --) {
    int a = anc[x][j];
    if(a != -1 && dep[a] >= dep[y]) {
      ans = std::min(ans, cost[x][j]);
      x = a;
    }
  }
  if(x == y) return ans;
  for(int j = 19; j >= 0; j --) {
    int a1 = anc[x][j], a2 = anc[y][j];
    if(a1 != -1 && a1 != a2) {
      ans = std::min(ans, cost[x][j]);
      ans = std::min(ans, cost[y][j]);
      x = a1; y = a2;
    }
  }
  ans = std::min(ans, std::min(cost[x][0], cost[y][0]));
  return ans;
}

char buf[maxn];
int main() {
  scanf("%d", &n);
  for(int i = 1; i <= n; i ++) {
    scanf("%s", buf + 1);
    for(int j = 1; j <= n; j ++) {
      if(buf[j] == '#') {
        dis[i][j] = 0;
      } else {
        dis[i][j] = std::min(std::min(i, n - i + 1), std::min(j, n - j + 1));
      }
    }
  }
  process();
  int q; scanf("%d", &q);
  while(q --) {
    int a, b, c, d; scanf("%d%d%d%d", &a, &b, &c, &d);
    printf("%d\n", query(id(a, b), id(c, d)));
  }
  return 0;
}