Language: C++

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define lb lower_bound
#define all(v) (v).begin(), (v).end()
#define at(a, b) get<b>(a)
typedef pair<int, int> PR;
typedef tuple<int, int, int> TP;
const int INF = 1 << 28;
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, -1, 0, 1};

struct UnionFind {
	vector<int> parent;
	
	UnionFind(int n){
		parent.resize(n);
		for (int i = 0; i < n; i++){
			parent[i] = i;
		}
	}
	
	int find(int x){
		if (parent[x] == x) return x;
		return parent[x] = find(parent[x]);
	}
	
	bool same(int x, int y){
		return find(x) == find(y);
	}
	
	bool unite(int x, int y){
		x = find(x);
		y = find(y);
		if (x == y) return false;
		parent[x] = y;
	}
};

int W, H, M, Q;
vector<int> px, py, qx, qy;
vector<int> sx, sy, gx, gy;
vector<int> xs, ys;
vector<vector<int> > grid;
vector<vector<int> > graph;

inline bool ok(int x, int y)
{
	return x > 0 && y > 0 && x < W - 1 && y < H - 1;
}

inline int conv(int x, int y)
{
	return x * H + y;
}

int solve(int s, int g)
{
	vector<int> dist(graph.size(), INF);
	dist[s] = 0;
	queue<PR> que;
	que.push(PR(s, 0));
	while (que.size()){
		PR pr = que.front(); que.pop();
		int pos = pr.first;
		int sum = pr.second;
		if (dist[pos] < sum) continue;
		if (pos == g) return sum;
		for (int i = 0; i < graph[pos].size(); i++){
			int to = graph[pos][i];
			if (dist[to] <= sum + 1) continue;
			dist[to] = sum + 1;
			que.push(PR(to, sum + 1));
		}
	}
	assert(0);
}

int main()
{
	scanf("%d %d %d", &W, &H, &M);
	px.resize(M);
	py.resize(M);
	qx.resize(M);
	qy.resize(M);
	
	px.pb(0);
	py.pb(0);
	qx.pb(W);
	qy.pb(0);
	
	px.pb(0);
	py.pb(0);
	qx.pb(0);
	qy.pb(H);
	
	px.pb(W);
	py.pb(0);
	qx.pb(W);
	qy.pb(H);
	
	px.pb(0);
	py.pb(H);
	qx.pb(W);
	qy.pb(H);
	
	for (int i = 0; i < M; i++){
		scanf("%d %d %d %d", &px[i], &py[i], &qx[i], &qy[i]);
		px[i] *= 2;
		py[i] *= 2;
		qx[i] *= 2;
		qy[i] *= 2;
		xs.pb(px[i] - 1);
		xs.pb(px[i]);
		xs.pb(px[i] + 1);
		xs.pb(qx[i] - 1);
		xs.pb(qx[i]);
		xs.pb(qx[i] + 1);
		ys.pb(py[i] - 1);
		ys.pb(py[i]);
		ys.pb(py[i] + 1);
		ys.pb(qy[i] - 1);
		ys.pb(qy[i]);
		ys.pb(qy[i] + 1);
	}
	for (int i = M; i < qx.size(); i++){
		px[i] *= 2;
		py[i] *= 2;
		qx[i] *= 2;
		qy[i] *= 2;
		xs.pb(px[i] - 1);
		xs.pb(px[i]);
		xs.pb(px[i] + 1);
		xs.pb(qx[i] - 1);
		xs.pb(qx[i]);
		xs.pb(qx[i] + 1);
		ys.pb(py[i] - 1);
		ys.pb(py[i]);
		ys.pb(py[i] + 1);
		ys.pb(qy[i] - 1);
		ys.pb(qy[i]);
		ys.pb(qy[i] + 1);
	}
	M = qx.size();
	scanf("%d", &Q);
	sx.resize(Q);
	sy.resize(Q);
	gx.resize(Q);
	gy.resize(Q);
	for (int i = 0; i < Q; i++){
		scanf("%d %d %d %d", &sx[i], &sy[i], &gx[i], &gy[i]);
		sx[i] *= 2;
		sy[i] *= 2;
		gx[i] *= 2;
		gy[i] *= 2;
		xs.pb(sx[i] - 1);
		xs.pb(sx[i]);
		xs.pb(sx[i] + 1);
		xs.pb(gx[i] - 1);
		xs.pb(gx[i]);
		xs.pb(gx[i] + 1);
		ys.pb(sy[i] - 1);
		ys.pb(sy[i]);
		ys.pb(sy[i] + 1);
		ys.pb(gy[i] - 1);
		ys.pb(gy[i]);
		ys.pb(gy[i] + 1);
	}
	sort(all(xs));
	xs.erase(unique(all(xs)), xs.end());
	sort(all(ys));
	ys.erase(unique(all(ys)), ys.end());
	W = xs.size();
	H = ys.size();
	for (int i = 0; i < M; i++){
		px[i] = lb(all(xs), px[i]) - xs.begin();
		py[i] = lb(all(ys), py[i]) - ys.begin();
		qx[i] = lb(all(xs), qx[i]) - xs.begin();
		qy[i] = lb(all(ys), qy[i]) - ys.begin();
	}
	for (int i = 0; i < Q; i++){
		sx[i] = lb(all(xs), sx[i]) - xs.begin();
		sy[i] = lb(all(ys), sy[i]) - ys.begin();
		gx[i] = lb(all(xs), gx[i]) - xs.begin();
		gy[i] = lb(all(ys), gy[i]) - ys.begin();
	}
	
	grid = vector<vector<int> >(W, vector<int>(H, 0));
	for (int i = 0; i < M; i++){
		for (int x = px[i]; x <= qx[i]; x++){
			for (int y = py[i]; y <= qy[i]; y++){
				grid[x][y] = 1;
			}
		}
	}
	
	UnionFind uf(W * H);
	graph = vector<vector<int> >(W * H, vector<int>());
	
	for (int x = 0; x < W; x++){
		for (int y = 0; y < H; y++){
			if (!ok(x, y)) continue;
			int nx, ny;
			nx = x + 1;
			ny = y;
			if (ok(nx, ny) && !grid[x][y] && !grid[nx][ny]){
				uf.unite(conv(x, y), conv(nx, ny));
			}
			nx = x;
			ny = y + 1;
			if (ok(nx, ny) && !grid[x][y] && !grid[nx][ny]){
				uf.unite(conv(x, y), conv(nx, ny));
			}
		}
	}
	
	for (int x = 0; x < W; x++){
		for (int y = 0; y < H; y++){
			if (!grid[x][y]) continue;
			if (!ok(x, y)) continue;
			int lx, ly, rx, ry, l, r;
			lx = x - 1;
			ly = y;
			rx = x + 1;
			ry = y;
			if (
			ok(lx, ly) && 
			ok(rx, ry) && 
			!grid[lx][ly] && 
			!grid[rx][ry] && 
			){
				l = uf.find(conv(lx, ly));
				r = uf.find(conv(rx, ry));
				if (!uf.same(l, r)){
					graph[l].pb(r);
					graph[r].pb(l);
				}
			}
			lx = x;
			ly = y - 1;
			rx = x;
			ry = y + 1;
			if (
			ok(lx, ly) && 
			ok(rx, ry) && 
			!grid[lx][ly] && 
			!grid[rx][ry] && 
			){
				l = uf.find(conv(lx, ly));
				r = uf.find(conv(rx, ry));
				if (!uf.same(l, r)){
					graph[l].pb(r);
					graph[r].pb(l);
				}
			}
		}
	}
	
	/*for (int i = 0; i < graph.size(); i++){
		for (int v : graph[i]){
			printf("%d ", v);
		}
		if (graph[i].size()) puts("");
	}*/
	
	/*for (int i = 0; i < W; i++){
		for (int j = 0; j < H; j++){
			printf("%d", grid[i][j]);
		}
		puts("");
	}*/
	
	for (int i = 0; i < Q; i++){
		int s = uf.find(conv(sx[i], sy[i]));
		int g = uf.find(conv(gx[i], gy[i]));
		printf("%d\n", solve(s, g));
	}
}

Compiler output:
a.cc: In function 'int main()':
a.cc:231:25: error: expected primary-expression before ')' token
  231 |                         ){
      |                         ^
a.cc:248:25: error: expected primary-expression before ')' token
  248 |                         ){
      |                         ^
a.cc: In member function 'bool UnionFind::unite(int, int)':
a.cc:36:27: warning: control reaches end of non-void function [-Wreturn-type]
   36 |                 parent[x] = y;