【題解】Zerojudge j125 - 4. 蓋步道

題目連結

題目大意

給定 $n \times n$ 的地圖，$(i, j)$ 的高度為 $h_{i, j}$。現在要你從 $(1, 1)$ 走到 $(n, n)$，並問你所有可行的路徑中，最大高度差的最小值是多少，和以最大高度差的最小值為前提的情況下的最短路徑？

• $1 \leq n \leq 300$
• $1 \leq h_{i, j} \leq 10^6$

題解

觀察到答案具有單調性，也就是假如高度差不超過 $d$ 可以從 $(1, 1)$ 走到 $(n, n)$，則高度差不超過 $d + 1$ 也可以達成。因此我們可以對答案二分搜，假設目前搜到 $d$，從 $(1, 1)$ 做 BFS 看能不能不經過高度差超過 $d$ 的路徑走到 $(n, n)$。最後輸出 $d$ 和最短路徑即可。實作細節請參考 code。

#include <bits/stdc++.h>
using namespace std;

const int d4i[] = {0, 1, 0, -1};
const int d4j[] = {1, 0, -1, 0};

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin >> n;
	vector<vector<int>> a(n, vector<int>(n));
	for(int i = 0; i < n; ++i) {
		for(int j = 0; j < n; ++j) {
			cin >> a[i][j];
		}
	}
	const int INF = (int) 1e9;
	auto f = [&](int k) {
		vector<vector<int>> dp(n, vector<int>(n, INF));
		dp[0][0] = 0;
		queue<pair<int, int>> que;
		que.emplace(0, 0);
		while(!que.empty()) {
			auto [i, j] = que.front();
			que.pop();
			for(int dir = 0; dir < 4; ++dir) {
				int ni = i + d4i[dir];
				int nj = j + d4j[dir];
				if(ni >= 0 && ni < n && nj >= 0 && nj < n && abs(a[i][j] - a[ni][nj]) <= k && dp[ni][nj] == INF) {
					dp[ni][nj] = dp[i][j] + 1;
					que.emplace(ni, nj);
				}
			}
		}
		return dp[n - 1][n - 1];
	};
	int ng = -1, ok = 1E6;
	while(ok - ng > 1) {
		int mid = (ng + ok) / 2;
		if(f(mid) < INF) {
			ok = mid;
		} else {
			ng = mid;
		}
	}
	cout << ok << "\n" << f(ok) << "\n";
	return 0;
}

如果本文對您有幫助的話幫忙點擊廣告和分享吧！

© 若無特別註明，本站文章皆由 WeakMouse's Coding Blog 原創 ，轉載引用本文前請先留言告知。本文轉載請註明文章源自 WeakMouse's Coding Blog ，作者 ，並附上原文連結： 【題解】Zerojudge j125 - 4. 蓋步道