P4771 八百标兵奔北坡 题解

· · 题解

可能更好的食用体验 | 题目传送门 | 我的其他题解

upd on 2024.10.16：润色码风，修改了因专栏更新而炸掉的 \LaTeX。

本题解写得比较细，作者的初衷是想给更多刚入门的新手 OIer 看，大佬们可根据自身需求忽略部分内容。

{\color{#00CD00}\text{题意简述}}

估计很多人都不太清晰题意，尤其是“北边”的含义。首先，“北边”指的是一个 {\text{babingbaboom}} 东北 45\degree 至西北 45\degree 的范围。例如，假设以下三个 5\times 5 的地图中蓝色表示一个 {\text{babingbaboom}} ，它可以奔到的范围为红色的区域：

以及“切比雪夫距离”，题目描述写的也不太清楚。它指的是一个点 (x_1,y_1) 与 (x_2,y_2) 之间的“切比雪夫距离”为 \max(\left|x_1-y_1\right|,\left|x_2-y_2\right|) 。

还有“山”的定义，只要一个点的高度比它东、南、西、北四个点的高度都要高（高度相等的不算），该点即为山。

弄明白这几点，这道题也就更容易着手了。

{\color{#00CD00}\text{主要思路}}

很多大佬这道题都是用 DP 做的，但这道题作为一道橙题，其实就是一道简单的枚举题。问题在于如何枚举。

假设在 (x,y) 处有一个 {\text{babingbaboom}}，我们来分析一下枚举的范围：

首先是行的枚举范围。通过上面的图示不难看出，行的范围即为 1\sim x。不过，为了更方便的枚举列（下面会讲到），我们将这个步骤改为枚举一个差 i，i 的范围是 0\sim x-1，此时的行数表示为 x-i。读到下面你就会明白为什么这样做了。

其次是列的枚举范围。可以发现，列的范围其实是与当前的行数有关的。有了前面枚举的差 i，列的范围可以表示为 y-i\sim y+i（注意还要判断一下是否超出边界）。

这样枚举下来，就能把每只 {\text{babingbaboom}} 所能去到的每个点都枚举出来。只要在这范围内发现山，根据“切比雪夫距离”，因为列的差值绝对不可能大于 i，所以此时的 i 即为答案。如果在这范围内没有一座山，则输出 Pool Babingbaboom!。

弄明白了如何枚举，其余细节请读者阅读代码，自行理解。

{\color{#00CD00}\text{完整代码}}

#include <bits/stdc++.h>
#define rep(i, a, b) for(int i=a; i<=b; i++)
#define ismountain(i, j)\
a[i][j]>a[i-1][j] && a[i][j]>a[i+1][j] && a[i][j]>a[i][j-1] && a[i][j]>a[i][j+1]
using namespace std;
const int N = 1e3 + 5;
int n, m, k, x, y;
int a[N][N], h[N][N];
int bbbb(int x, int y){
    rep(i, 0, x-1) rep(j, max(0, y-i), min(m, y+i)) //枚举每个 Babingbaboom 可以到达的位置
        if(h[x-i][j]) return i; //找到一座山，i 即为答案
    return -1; //-1 表示在此范围内没有山 
}
int main(){
    ios::sync_with_stdio(false), cin.tie(nullptr);
    cin >> n >> m >> k;
    rep(i, 1, n) rep(j, 1, m) cin >> a[i][j];
    rep(i, 1, n) rep(j, 1, m) h[i][j] = ismountain(i,j); // 预处理
    rep(i, 1, k){
        cin >> x >> y;
        int ans = bbbb(x, y);
        if(ans != -1) cout << ans << "\n";
        else cout << "Pool Babingbaboom！\n";
    }
    return 0;
}