Ta dùng phương pháp chia để trị để giải quyết bài toán này.

Xét đoạn mã sau:

void solve (tập S, cực trái l, cực phải r) {
        if (r > l hoặc tập S rỗng) return
        int mid = (r+l)/2
        for (int i=1; i<=n; i++) {
            dijkstra (l,r,i,mid) (thực hiện thuật toán dijkstra từ ô (i,mid) ra tất cả các ô có cột trong đoạn [l,r])
            Cập nhật mọi truy vấn trong tập S, giả định rằng đường đi tối ưu từ (x,y) --> (u,v) sẽ đi qua ô (i,mid)
         }
         Tập trái = những truy vấn trong tập s có max(y,v) < mid
         Tập phải = những truy vấn trong tập s có min(y,v) > mid
         solve (Tập trái, l, mid-1)
         solve (Tập phải, mid+1, r)
}

Như vậy, với mỗi lần đệ quy, ta sẽ $dijkstra$ $n$ lần. Tuy nhiên, mỗi lần thực hiện $dijkstra$ ta chỉ giới hạn trong đoạn $[l,r]$. Tức thực tế, ta chỉ cần $dijkstra$ qua tổng cộng $n*m*log_n$ ô.

Tuy vậy 

Với trường hợp này (hai ô màu xanh lá là truy vấn đang xét, hai đường thẳng màu đỏ là hai biên, đường thẳng màu cam là hàng $mid$, đường đi màu xanh nước biển là đường đi tối ưu), ta nhận thấy rằng việc chỉ $dijkstra$ trong khoảng $[l,r]$ dẫn tới việc các ô trong hàng $mid$ không thể đi theo đường màu xanh nước biển để tạo ra đường đi tối ưu, liệu nó có dẫn tới việc không thể cập nhật kết quả tối ưu? Câu trả lời là không. Thật vậy, ở lần đầu ta gọi hàm $solve(S,1,n)$, không thể có đường đi nào ra ngoài bảng. Tiếp theo tới đệ quy cho tập con trái, giả sử có một đường đi tối ưu phải ra ngoài khoảng $[l,mid-1]$, vậy nó buộc phải đi qua ô $mid$, tức là ta đã xét tới nó rồi. Tương tự với tập con bên phải. Như vậy hàm trên hoàn toàn đúng.

Code:

#include<bits/stdc++.h>
using namespace std;
const int N = 5005;
int n,m,Q;	
const int M = 30050;
struct qr {
	int x,y,u,v,id;
};
int a[8][N];
int res[M];
struct vcl {
	int u,v,val;
	bool operator < (const vcl &o) const {
		return val > o.val;
	}
};
int mx[] = {0,1,-1,0};
int my[] = {1,0,0,-1};
int f[8][N];
const int inf = 2e9;
bool valid (int x, int y, int l, int r) {
	return (x >= 1 && x <= n && y >= l && y <= r);
}
void dijkstra (int l, int r, int st, int mid) {
	priority_queue<vcl> pq;
	pq.push({st,mid,0});
	for (int i=1; i<=n; i++) {
		for (int j=l; j<=r; j++) f[i][j] = inf;
	}
	f[st][mid] = 0;
	while (pq.size()) {
		vcl dak = pq.top();
		pq.pop();
		int u = dak.u, v = dak.v, val = dak.val;
		if (val > f[u][v]) continue;
		for (int i=0; i<4; i++) {
			int x = u + mx[i];
			int y = v + my[i];
			if (!valid(x,y,l,r)) continue;
			if (f[x][y] > f[u][v] + a[x][y]) {
				f[x][y] = f[u][v] + a[x][y];
				pq.push({x,y,f[x][y]});
			}
		}
	}
}
void solve (vector<qr> s, int l, int r) {
	if (s.size() == 0 || (l > r)) return;
	int mid = (r+l) >> 1;
	for (int i=1; i<=n; i++) {
		dijkstra (l,r,i,mid);
		for (qr dak : s) {
			int x = dak.x, y = dak.y, u = dak.u, v = dak.v;
			int id = dak.id;
			res[id] = min (res[id],f[x][y]+f[u][v]+a[i][mid]);
		}
	}
	vector<qr> lef,rig;
	for (qr dak : s) {
		int x = dak.x, y = dak.y, u = dak.u, v = dak.v;
		int id = dak.id;
		if (max(y,v) < mid) lef.push_back(dak);
		if (min(y,v) > mid) rig.push_back(dak);
	}
	solve (lef,l,mid-1);
	solve (rig,mid+1,r);
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> m;
	for (int i=1; i<=n; i++) {
		for (int j=1; j<=m; j++) cin >> a[i][j];
	}
	vector<qr> s;
	cin >> Q;
	for (int i=1; i<=Q; i++) {
		int x,y,u,v; cin >> x >> y >> u >> v;
		s.push_back({x,y,u,v,i});
		res[i] = 2e9;
	}
	solve (s,1,m);
	for (int i=1; i<=Q; i++){
		cout << res[i] << '\n';
	}
}