Link。
感谢苏泊尔的题解，一点补充。
首先呢，可以处理出中心在每个格子 \((x, y)\) 上的最大边长 \(d_{x, y}\)。这个用一下二维前缀和统计 # 的个数再简单二分一下就好了，注意不能出界。
然后呢我们只能上下左右移动，考虑转化成一个图论问题（？）。所以就直接相邻的格子连边就好了，因为是双向边所以可以只连两个方向。那么边权自然就是两者 \(d\) 的最小值。这样的话，\((r_A, c_A) \to (r_B, c_B)\) 的路径上集装箱的最大尺寸就相当于走过的边的最小值。即答案就是 \((r_A, c_A) \to (r_B, c_B)\) 的路径上边的最小值的最大值，是一个最大瓶颈路。
当然 OI Wiki 给出的是最小瓶颈路，本质是一样的。具体怎么实现呢？
根据最小生成树定义，\(x\) 到 \(y\) 的最小瓶颈路上的最大边权等于最小生成树上 \(x\) 到 \(y\) 路径上的最大边权。
那么我们在跑 Kruskal 的时候，把选中的边新建成一棵树，\(x\) 到 \(y\) 的最小瓶颈路上的最大边权就相当于这棵树上 \(x \to y\) 路径的最大边权。这个很好维护，就是在维护 lca \(k\) 层父亲节点 \(fa_{u, k}\) 的基础上多维护一个 \(dis\)，\(dis_{u, k}\) 表示从 \(u \to fa_{u, k}\) 的路径上的最大边权，拆成 \(u \to fa_{u, k - 1}\) 和 \(fa_{u, k - 1} \to fa_{u, k}\)，转移就是 \(dis_{u, k} = \max(dis_{u, k - 1}, dis_{fa_{u, k - 1}, k - 1})\)。具体询问两点就是在跳 lca 的时候更新答案，应该比较 naive，可以直接看代码。
然后基本就做完了。注意可能有多个连通块所以要对每个没有访问过的点都 dfs 一遍。以及做的是最大瓶颈路所以反过来求最大生成树，然后转移改成 \(\min\) 啥的就好了。
namespace liuzimingc {
const int N = 1e3 + 5, M = 2e6 + 5, K = 1e6 + 5;
#define endl '\n'
int n, q, s[N][N], d[N][N], m, fa[K], f[K][21], dis[K][21], dep[K];
bool vis[K];
char str[N][N];
vector<pair<int, int>> e[K];
struct node {
int u, v, w;
} edge[M];
int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
int get_id(int x, int y) { return (x - 1) * n + y; }
int get(int x1, int y1, int x2, int y2) {
return s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1];
}
void dfs(int u, int fa, int l) {
if (vis[u]) return;
vis[u] = true;
dep[u] = dep[fa] + 1;
f[u][0] = fa;
dis[u][0] = l;
for (int i = 1; i <= 20; i++) {
f[u][i] = f[f[u][i - 1]][i - 1];
dis[u][i] = min(dis[u][i - 1], dis[f[u][i - 1]][i - 1]);
}
for (const auto &i : e[u]) {
int v = i.first, w = i.second;
if (v == fa) continue;
dfs(v, u, w);
}
}
int lca(int x, int y) { // not actully works as it looks you know
if (dep[x] > dep[y]) swap(x, y);
int ans = 0x3f3f3f3f;
for (int i = 20; ~i; i--)
if (dep[f[y][i]] >= dep[x]) ans = min(ans, dis[y][i]), y = f[y][i];
if (x == y) return ans;
for (int i = 20; ~i; i--)
if (f[x][i] != f[y][i]) ans = min(ans, min(dis[x][i], dis[y][i])), x = f[x][i], y = f[y][i];
return min(ans, min(dis[x][0], dis[y][0]));
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
cin >> n;
for (int i = 1; i <= n; i++) cin >> (str[i] + 1);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + (str[i][j] == '#');
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++) {
if (str[i][j] == '#') {
d[i][j] = -1;
continue;
}
int l = 0, r = min({ i - 1, j - 1, n - i, n - j });
while (l < r) {
int mid = l + r + 1 >> 1;
if (get(i - mid, j - mid, i + mid, j + mid)) r = mid - 1;
else l = mid;
}
d[i][j] = l;
}
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++) {
if (i < n && ~min(d[i][j], d[i + 1][j])) edge[++m] = (node){ get_id(i, j), get_id(i + 1, j), min(d[i][j], d[i + 1][j]) };
if (j < n && ~min(d[i][j], d[i][j + 1])) edge[++m] = (node){ get_id(i, j), get_id(i, j + 1), min(d[i][j], d[i][j + 1]) };
} // 两个方向即可
for (int i = 1; i <= n * n; i++) fa[i] = i;
sort(edge + 1, edge + 1 + m, [](node a, node b){ return a.w > b.w; }); // 最大生成树
for (int i = 1; i <= m; i++) {
int x = find(edge[i].u), y = find(edge[i].v);
if (x == y) continue;
fa[x] = y;
e[edge[i].u].push_back(make_pair(edge[i].v, edge[i].w));
e[edge[i].v].push_back(make_pair(edge[i].u, edge[i].w));
}
for (int i = 1; i <= n * n; i++)
if (!vis[i]) dfs(i, 0, 0); // 保证每个联通块都搜到
cin >> q;
while (q--) {
int ra, ca, rb, cb;
cin >> ra >> ca >> rb >> cb;
if (find(get_id(ra, ca)) != find(get_id(rb, cb))) cout << 0 << endl; // 不连通
else cout << 1 + 2 * lca(get_id(ra, ca), get_id(rb, cb)) << endl;
}
return 0;
}
} // namespace liuzimingc