自动搬运

查看原文

来自洛谷，原作者为

	Spectator 我趁有半天空档 ／ 为你跑一趟 ／ 城市里永远有宝藏

搬运于2025-08-24 22:03:27，当前版本为作者最后更新于2021-12-07 18:08:38，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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

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