SP733 题解

前言

题目传送门！

更好的阅读体验？

校内比赛题。赶紧补篇题解。

思路

经典的二分加搜索。

由于 \(h_{i, j}\) 范围很小，考虑二分答案。

二分答案的范围应该是 \([0, 110]\)。

对于 \(\texttt{check()}\) 函数，可以暴力枚举所有差为 \(\texttt{mid}\) 的数对，并使用 bfs 强行搜索检验。

bfs 比较容易实现，重点在于 \(\texttt{check()}\) 的枚举。

我们明显可以枚举所有数对的较小值 \(k\)，较大值自然就是 \((k + \texttt{mid})\)。

但是直接这样枚举太过鲁莽，可以剪枝。

注意到 \(h_{1, 1}\) 与 \(h_{n, n}\) 是必定会经过的。

数对较大值的最小值，应该是 \(\max(h_{1, 1}, h_{n, n})\)。

因此可得，数对较小值的最小值，应该是 \(\max(h_{1, 1}, h_{n, n}) - \texttt{mid}\)。

再来看数对较小值的最大值，它是 \(\min(h_{1, 1}, h_{n, n})\)。这个稍微有点难想。

完整代码

#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
#define N 105
using namespace std;
int n, a[N][N];
int Max, Min;
void Input()
{
	scanf("%d", &n);
	if (n == 1) //关键特判。
	{
		printf("0");
		exit(0);
	}
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			scanf("%d", &a[i][j]);
	Max = max(a[1][1], a[n][n]);
	Min = min(a[1][1], a[n][n]);
}
struct Node
{
	int x, y;
};
int dict[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
bool vis[N][N];
bool bfs(int minn, int maxn) //非常模板的 bfs 只是要判一下数的范围。
{
	memset(vis, false, sizeof(vis)); //切记清空数组！
	queue <Node> Q;
	Q.push( (Node){1,1} );
	vis[1][1] = true;
	while (!Q.empty())
	{
		int x = Q.front().x, y = Q.front().y;
		Q.pop();
		if (x == n && y == n) return true;
		for (int i = 0; i < 4; i++)
		{
			int dx = x + dict[i][0], dy = y + dict[i][1];
			if (!(1 <= dx && dx <= n && 1 <= dy && dy <= n)) continue;
			if (vis[dx][dy]) continue;
			if (minn <= a[dx][dy] && a[dx][dy] <= maxn) //唯一和板子不一样的地方。
			{
				vis[dx][dy] = true;
				Q.push( (Node){dx, dy} );
			}
		}
	}
	return false;
}
bool chk(int ans) //较难理解。
{
	int l = Max - ans, r = Min;
	for (int i = l; i <= r; i++)
		if (bfs(i, i + ans))
			return true;
	return false;
}
int FIND()
{
	int pos = -1, L = 0, R = 110;
	while (L < R)
	{
		int mid = (L + R) >> 1;
		if (chk(mid)) R = mid, pos = R; //答案求最大值，pos 应该在 R 这一边更新。
		else L = mid + 1;
	}
	return pos;
}
int main()
{
	Input();
	printf("%d", FIND());
	return 0;
}

希望能帮助到大家！
首发：2022-07-25 12:11:14