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;
}

希望能帮助到大家！