Description
给定一个 \(n\times n\) 的网格图，其中部分格点有障碍物使得箱子不能置于其上。规定箱子是一个奇数边长的正方形，其坐标为其中心格点的坐标。箱子只能上下左右移动，每次询问从一个格点能移动到另一个格点的最大箱子。
Solution
首先对于每个点 \((x,y)\) 用二分求出以这个点为中心格点的最大边长 \(d[x][y]\)，是 \(O(n^2\log n)\) 的。
然后发现这是多组询问，所以不能暴力。
先把这个看成一个普通的无向图，把相邻的格点连无向边，边权为两个点的 \(d\) 值取较小值，那么相当于就是询问图上两点的最大瓶颈路径。
这个东西可以用 Kruskal 先跑出最大生成树，然后最大瓶颈路径就是这两点的树上最短路径。
证明：
先看到 Kruskal 过程：将边权从大到小排序，然后枚举，如果加上当前边不会出现环，就加边。相当于就是能连边就连边。
假设 \(u\) 和 \(v\) 所在集合在枚举到从大到小第 \(k\) 条边时第一次被合并，如果 \(u\) 和 \(v\) 的最大瓶颈路径小于当前边权，那么这相当于在这条边之前 \(u\) 和 \(v\) 的集合已经被合并了，那么这与假设矛盾。所以 Kruskal 跑出来的最大生成树就是最大瓶颈生成树。
注意：这可能是个森林，所以要对于每棵树都跑一遍最大生成树。
建完最大生成树后，询问就转化为求树上两点路径的最小边权，直接倍增 LCA 即可，每次是 \(O(\log n)\) 的。
于是整个程序复杂度就为 \(O(n^2\log n)\)，由于时限开的很大，所以可以轻松通过。
Code
代码
#include <bits/stdc++.h>
#ifdef ORZXKR
#include <debug.h>
#else
#define debug(...) 1
#endif
using namespace std;
namespace FASTIO {
char ibuf[1 << 21], *p1 = ibuf, *p2 = ibuf;
char getc() {
return p1 == p2 && (p2 = (p1 = ibuf) + fread(ibuf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++;
}
template<class T> bool read(T &x) {
x = 0; int f = 0; char ch = getc();
while (ch < '0' || ch > '9') f |= ch == '-', ch = getc();
while (ch >= '0' && ch <= '9') x = (x * 10) + (ch ^ 48), ch = getc();
x = (f ? -x : x); return 1;
}
bool read(char &x) {
while ((x = getc()) == ' ' || x == '\n' || x == '\r');
return x != EOF;
}
bool read(char *x) {
while ((*x = getc()) == '\n' || *x == ' ' || *x == '\r');
if (*x == EOF) return 0;
while (!(*x == '\n' || *x == ' ' || *x == '\r' || *x == EOF)) *(++x) = getc();
*x = 0;
return 1;
}
template<typename A, typename ...B> bool read(A &x, B &...y) { return read(x) && read(y...); }
char obuf[1 << 21], *o1 = obuf, *o2 = obuf + (1 << 21) - 1;
void flush() { fwrite(obuf, 1, o1 - obuf, stdout), o1 = obuf; }
void putc(char x) { *o1++ = x; if (o1 == o2) flush(); }
template<class T> void write(T x) {
if (!x) putc('0');
if (x < 0) x = -x, putc('-');
char c[40]; int tot = 0;
while (x) c[++tot] = x % 10, x /= 10;
for (int i = tot; i; --i) putc(c[i] + '0');
}
void write(char x) { putc(x); }
template<typename A, typename ...B> void write(A x, B ...y) { write(x), write(y...); }
struct Flusher {
~Flusher() { flush(); }
} flusher;
} // namespace FASTIO
using FASTIO::read; using FASTIO::putc; using FASTIO::write;
const int kMaxN = 1e3 + 5, kMaxS = 1e6 + 5, dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};
class DSU {
public:
void init(int n) {
for (int i = 1; i <= n; ++i) {
fa[i] = i;
}
}
int find(int x) {
return x == fa[x] ? x : fa[x] = find(fa[x]);
}
void unionn(int x, int y) {
int fx = find(x), fy = find(y);
if (fx != fy) fa[fx] = fy;
}
private:
int fa[kMaxS];
} d;
int n, q, yxy;
int dis[kMaxS];
char s[kMaxN][kMaxN];
vector<pair<int, int>> G[kMaxS];
int getid(int x, int y) {
return (x - 1) * n + y;
}
void addE(int u, int v, int w) {
G[u].emplace_back(v, w);
}
namespace GETDIS {
int sum[kMaxN][kMaxN], d[kMaxN][kMaxN];
queue<pair<int, int>> q;
int get(int m1, int n1, int m2, int n2) {
return sum[m2][n2] - sum[m1 - 1][n2] - sum[m2][n1 - 1] + sum[m1 - 1][n1 - 1];
}
void solve() {
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + (s[i][j] == '#');
}
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
if (s[i][j] == '#') continue ;
int L = 0, R = min({i - 1, n - i, j - 1, n - j}) + 1, res = 0;
while (L + 1 < R) {
int mid = (L + R) >> 1;
if (!get(i - mid, j - mid, i + mid, j + mid)) L = res = mid;
else R = mid;
}
d[i][j] = dis[getid(i, j)] = 2 * res + 1;
}
}
}
} // namespace GETDIS
namespace KRUSKAL {
struct Edge {
int u, v, w;
} ed[kMaxS << 2];
DSU dd;
int tot, cnt[kMaxS], tt[kMaxS], fa[kMaxS];
void build() {
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
if (s[i][j] == '#') continue ;
for (int k = 0; k < 2; ++k) {
int tx = i + dx[k], ty = j + dy[k];
if (tx < 1 || tx > n || ty < 1 || ty > n || s[tx][ty] == '#') continue ;
int u = getid(i, j), v = getid(tx, ty), w = min(dis[u], dis[v]);
ed[++tot] = {u, v, w}, d.unionn(u, v);
}
}
}
}
void solve() {
d.init(n * n), dd.init(n * n), build();
for (int i = 1; i <= n * n; ++i) {
if (dis[i]) ++tt[fa[i] = d.find(i)];
}
sort(ed + 1, ed + 1 + tot, [&] (Edge e1, Edge e2) { return e1.w > e2.w; });
for (int i = 1; i <= tot; ++i) {
int fu = dd.find(ed[i].u), fv = dd.find(ed[i].v);
if (fu != fv) {
if (cnt[fa[ed[i].u]] == tt[fa[ed[i].u]] - 1) continue ;
dd.unionn(ed[i].u, ed[i].v);
addE(ed[i].u, ed[i].v, ed[i].w), addE(ed[i].v, ed[i].u, ed[i].w);
++cnt[fa[ed[i].u]];
}
}
}
} // namespace KRUSKAL
namespace LCA {
int lg[kMaxS], dep[kMaxS], mi[kMaxS][22], fa[kMaxS][22];
void getlg() {
memset(mi, 0x3f, sizeof(mi));
lg[0] = -1;
for (int i = 1; i <= n * n; ++i) {
lg[i] = lg[i >> 1] + 1;
}
}
void dfs(int u, int fat, int lw) {
dep[u] = dep[fat] + 1, fa[u][0] = fat, mi[u][0] = lw;
for (int i = 1; i <= lg[n * n]; ++i) {
fa[u][i] = fa[fa[u][i - 1]][i - 1];
mi[u][i] = min(mi[u][i - 1], mi[fa[u][i - 1]][i - 1]);
}
for (auto [v, w] : G[u]) {
if (v == fat) continue ;
dfs(v, u, w);
}
}
int LCA(int x, int y) {
if (dep[x] < dep[y]) swap(x, y);
for (int i = lg[n * n]; ~i; --i) {
if (dep[fa[x][i]] >= dep[y]) {
x = fa[x][i];
}
}
if (x == y) return x;
for (int i = lg[n * n]; ~i; --i) {
if (fa[x][i] != fa[y][i]) {
x = fa[x][i], y = fa[y][i];
}
}
return fa[x][0];
}
int getmx(int x, int y) {
int lca = LCA(x, y), ret = 1e9;
for (int i = lg[n * n]; ~i; --i) {
if (dep[fa[x][i]] > dep[lca]) ret = min(ret, mi[x][i]), x = fa[x][i];
if (dep[fa[y][i]] > dep[lca]) ret = min(ret, mi[y][i]), y = fa[y][i];
}
if (x != lca) ret = min(ret, mi[x][0]);
if (y != lca) ret = min(ret, mi[y][0]);
return ret;
}
} // namespace LCA
int main() {
#ifdef ORZXKR
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
read(n);
for (int i = 1; i <= n; ++i) {
read(s[i] + 1);
}
GETDIS::solve(), KRUSKAL::solve(), LCA::getlg();
for (int i = 1; i <= n * n; ++i) {
if (dis[i] && d.find(i) == i) {
LCA::dfs(i, 0, 1e9);
}
}
read(q);
while (q--) {
int s1, t1, s2, t2;
read(s1, t1, s2, t2);
int u = getid(s1, t1), v = getid(s2, t2);
if (d.find(u) == d.find(v)) write(LCA::getmx(getid(s1, t1), getid(s2, t2)), '\n');
else write(0, '\n');
}
return 0;
}