CERC2016 Hangar Hurdles

简单题。

每个点 \((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;
}