简单题。
每个点 \((i,j)\) 二分处理出 \(p_{i,j}\) 表示在这个点上面能放的最大的集装箱大小，这部分二分就可以做到 \(O(n^2\log n)\)。
然后就相当于选择一条从 \((A_x,A_y)\) 到 \((B_x,B_y)\) 的路径，使得路径上 \(p\) 值最小的点最大。
这是经典套路，对网格图建最大生成树，答案就相当于两点之间权值的最小值，可以 \(O(n^2)-O(\log n)\) 树链剖分维护。
复杂度 \(O(n^2\log n)\)，常数写小一点就能过了。如果被卡了可以考虑缩点，把 \(p\) 值相同的缩在一起，然后再跑最大生成树，就过了。
缩点代码：
#include <bits/stdc++.h>
using namespace std;
namespace vbzIO {
char ibuf[(1 << 20) + 1], *iS, *iT;
// #if ONLINE_JUDGE
// #define gh() (iS == iT ? iT = (iS = ibuf) + fread(ibuf, 1, (1 << 20) + 1, stdin), (iS == iT ? EOF : *iS++) : *iS++)
// #else
#define gh() getchar()
// #endif
#define mt make_tuple
#define mp make_pair
#define fi first
#define se second
#define pc putchar
#define pb push_back
#define ins insert
#define era erase
typedef tuple<int, int, int> tu3;
typedef pair<int, int> pi;
inline int rd() {
char ch = gh();
int x = 0;
bool t = 0;
while (ch < '0' || ch > '9') t |= ch == '-', ch = gh();
while (ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (ch ^ 48), ch = gh();
return t ? ~(x - 1) : x;
}
inline void wr(int x) {
if (x < 0) {
x = ~(x - 1);
putchar('-');
}
if (x > 9)
wr(x / 10);
putchar(x % 10 + '0');
}
}
using namespace vbzIO;
const int N = 1e3 + 100;
int n, q, tot, dfc, a[N][N], s[N][N], mx[N][N], bel[N][N], vis[N][N], pr[N * N], f[N * N][20];
int fa[N * N], sz[N * N], son[N * N], dep[N * N], top[N * N], id[N * N], vs[N * N], anc[N * N], wt[N * N];
int fx[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
char c[N][N];
vector<pi> g[N * N];
vector<tu3> ed;
int getf(int x) { return x == pr[x] ? x : pr[x] = getf(pr[x]); }
int cnt(int lx, int rx, int ly, int ry) { return s[rx][ry] - s[lx - 1][ry] - s[rx][ly - 1] + s[lx - 1][ly - 1]; }
void dfs(int x, int y) {
vis[x][y] = 1, bel[x][y] = tot;
for (int k = 0; k <= 3; k++) {
int xx = x + fx[k][0];
int yy = y + fx[k][1];
if (!xx || !yy || xx > n || yy > n || vis[xx][yy] || a[xx][yy] || mx[xx][yy] != mx[x][y]) continue;
dfs(xx, yy);
}
}
void dfs1(int u, int fat) {
fa[u] = fat, anc[u] = anc[fat];
dep[u] = dep[fat] + 1, vs[u] = sz[u] = 1;
for (auto [v, w] : g[u]) {
if (v == fat) continue;
dfs1(v, u), sz[u] += sz[v], wt[v] = w;
if (sz[v] > sz[son[u]]) son[u] = v;
}
}
void dfs2(int u, int pre) {
top[u] = pre, id[u] = ++dfc;
if (son[u]) dfs2(son[u], pre);
for (auto [v, w] : g[u]) {
if (v == son[u] || v == fa[u]) continue;
dfs2(v, v);
}
}
int qw(int l, int r) {
int len = log2(r - l + 1);
return min(f[l][len], f[r - (1 << len) + 1][len]);
}
int qry(int u, int v) {
int res = n + 1;
while (top[u] != top[v]) {
if (dep[top[u]] < dep[top[v]]) swap(u, v);
res = min(res, qw(id[top[u]], id[u])), u = fa[top[u]];
}
if (dep[u] > dep[v]) swap(u, v);
return u == v ? res : min(res, qw(id[u] + 1, id[v]));
}
int main() {
n = rd();
for (int i = 1; i <= n; i++)
scanf("%s", c[i] + 1);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
a[i][j] = c[i][j] == '#' ? 1 : 0;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
s[i][j] = s[i - 1][j] + a[i][j];
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
s[i][j] += s[i][j - 1];
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
int l = 1, r = min(min(i, n - i + 1), min(j, n - j + 1));
while (l <= r) {
int mid = (l + r) >> 1;
if (cnt(i - mid + 1, i + mid - 1, j - mid + 1, j + mid - 1)) r = mid - 1;
else l = mid + 1, mx[i][j] = mid;
}
mx[i][j] = 2 * mx[i][j] - 1;
}
}
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
if (!vis[i][j] && !a[i][j]) tot++, dfs(i, j);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (a[i][j]) continue;
for (int k = 0; k <= 3; k++) {
int x = i + fx[k][0];
int y = j + fx[k][1];
if (!x || !y || x > n || y > n || a[x][y] || mx[i][j] == mx[x][y]) continue;
ed.pb(mt(min(mx[i][j], mx[x][y]), bel[x][y], bel[i][j]));
}
}
}
sort(ed.begin(), ed.end(), greater<tu3> ());
ed.erase(unique(ed.begin(), ed.end()), ed.end());
for (int i = 1; i <= tot; i++) pr[i] = i;
for (auto [w, u, v] : ed) {
int pu = getf(u), pv = getf(v);
if (pu == pv) continue;
pr[pu] = pv, g[u].pb(mp(v, w)), g[v].pb(mp(u, w));
}
for (int i = 1; i <= tot; i++)
if (!vs[i]) anc[0] = i, dfs1(i, 0), dfs2(i, i);
for (int i = 1; i <= tot; i++) f[id[i]][0] = wt[i];
for (int j = 1; (1 << j) <= tot; j++)
for (int i = 1; i <= tot; i++)
f[i][j] = min(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
q = rd();
while (q--) {
int i = rd(), j = rd(), x = rd(), y = rd(), res;
if (anc[bel[i][j]] != anc[bel[x][y]]) res = 0;
else if (bel[i][j] == bel[x][y]) res = mx[i][j];
else res = qry(bel[i][j], bel[x][y]);
// cout << bel[i][j] << " " << bel[x][y] << endl;
wr(res), puts("");
}
return 0;
}