因为 $nm$ 很小，有多种解法，给出一种容易实现的。

• 建立所有 $\Theta(n^2m^2)$ 条边
• 从小到大跑 Kruskal，过程中，若长为 $k$ 的边使得两个集合 $A,B$ 合并，则对于每一对 $\{(a,b)|a\in A,b\in B\}$ ，使得 $a,b$ 联通的最小代价是 $k$。
• 这样每次回答都是 $\Theta(1)$，时间复杂度是 $\Theta(\alpha(n^2m^2)\times n^2m^2+q)$。

#include <bits/stdc++.h>
using namespace std;
using ll = long long int;

struct dsu {
	dsu(int n) : p(n + 1), v(n + 1) { for(int i = 1; i <= n; i++) p[i] = i, v[i] = {i}; }
	
	int find(int x) { if(x != p[x]) p[x] = find(p[x]); return p[x]; }
	void merge(int x, int y) { 
		x = find(x); y = find(y);
		if(v[x].size() < v[y].size()) swap(x, y);
		v[x].insert(v[x].end(), v[y].begin(), v[y].end());
		v[y].clear();
		p[y] = x; 
	}
	
	vector<int> p;
	vector<vector<int>> v;
};

void solve()
{
	int n, m; cin >> n >> m;
	vector<string> s(n + 1);

	
	map<int, vector<array<int, 4>>> edges;
	
	for(int i = 1; i <= n; i++) cin >> s[i], s[i] = " " + s[i];
	
	for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) {
		if(s[i][j] == 'x') continue;
		for(int p = i; p <= n; p++) for(int q = 1; q <= m; q++) {
			if(s[p][q] == 'x') continue;
			if(i == p && j == q) continue;
			edges[(p - i) * (p - i) + (q - j) * (q - j)].push_back({i, j, p, q});
		}
	}
	
	dsu d(n * m);
	
	vector ans(n * m + 1, vector(n * m + 1, 0));
	
	long long sum = 0;
	for(auto [dis, _] : edges) {
		for(auto [sx, sy, tx, ty] : _) {
			int S = (sx - 1) * m + sy, T = (tx - 1) * m + ty;			
			if(d.find(S) == d.find(T)) continue;
			for(auto u : d.v[d.find(S)]) for(auto v : d.v[d.find(T)]) {
				ans[u][v] = ans[v][u] = dis;
			} 
			d.merge(S, T);
		}
	}
	
	
	int q; cin >> q;
	while(q--) {
		int sx, sy, tx, ty;
		cin >> sx >> sy >> tx >> ty;
		int S = (sx - 1) * m + sy, T = (tx - 1) * m + ty;
		cout << ans[S][T] << '\n';
	}
}
int main()
{
	ios::sync_with_stdio(false); cin.tie(nullptr);
//	int t; cin >> t; while(t--)
	solve();
	return 0;
}