Submission #63176966

---

Source Code Expand

#include <bits/stdc++.h>
//#define int long long 
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define fr first
#define se second
#define endl '\n'
#define pb push_back
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
mt19937_64 rnd(time(0));

const int N = 2e5 + 10;

int n, m, q;
int h[510][510];
map<pair<pii,pii>,int> ans;
int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1};


void BFS(int X, int Y){
	priority_queue<array<int,3>> pq;
	ans[{{X,Y},{X,Y}}] = h[X][Y];
	pq.push({h[X][Y], X, Y});
	while(pq.size()){
		auto [H, x, y] = pq.top();
		pq.pop();
		for(int k = 0; k < 4; k ++){
			int tx = x + dx[k];
			int ty = y + dy[k];
			if(tx <= 0 || ty <= 0 || tx > n || ty > m || ans.count({{X,Y},{tx,ty}})) continue;
			ans[{{X,Y},{tx,ty}}] = min(H, h[tx][ty]);
			pq.push({ans[{{X,Y},{tx,ty}}], tx, ty});
		}
	} 
}

void solve()
{
	cin >> n >> m;
	for(int i = 1; i <= n; i ++){
		for(int j = 1; j <= m; j ++){
			cin >> h[i][j];
		}
	}
	
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j ++){
			BFS(i, j);
		}
	}

	// cout << ans.count({{1,1},{3,1}}) << endl;
	// return;

	cin >> q;
	while(q--){
		int a, b, y, c, d, z;
		cin >> a >> b >> y >> c >> d >> z;
		int H = ans[{{a,b},{c,d}}];
		// cout << H << endl;
		if(y <= H){ // 可以直接到(c,d)
			cout << abs(z - y) << endl;
		}
		else{ // 必须先下楼到H,再到z
			cout << (y - H) + abs(z - H) << endl;
		}
	}
}


signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	int T=1; //cin>>T;
	while(T--) solve();
	return 0;
}

Submission Info

Judge Result