B3662 [语言月赛202209] 山峰 題解

· · 题解

B3662 [语言月赛202209] 山峰 題解

Source & Knowledge

2022 年 9 月语言月赛，由洛谷网校入门计划 / 基础计划提供。

本题考察对二维数组的掌握与运用。

文字题解

题目大意

给定 n \times m 大小的矩阵和 T 次操作，每次操作给定 2 个坐标交换他们的值，最后求有几个坐标的值比上下左右的值大（即山峰），并输出这几个坐标。

解析

我们把这道题拆成四个步骤：读入数据、交换操作、输出山峰个数，输出山峰坐标。

读入数据：

观察到，本题的数据范围为 1 \le n,m \le 1000,0\le T \le 10^5，读入量超过 1000 \times 1000 + 10^5 \times 4 ，所以我们可以使用 scanf 来读入数据，或关闭同步流来加快 std::cin 的速度。

交换操作：

将 2 个数据交换，可以想象成交换 2 个盒子内的物品，需要拿第三个盒子来暂放物品，操作如下表所示：

盒子 1 盒子 2 盒子 3
初始 x y 空
第一次操作 空 y x
第二次操作 y 空 x
第三次操作 y x 空

转换成 C++ 语言，即：tmp=x; x=y; y=tmp;。

在这里，推荐另一个更快的方法，使用 std::swap(int x,int y) 函数，其中 x 和 y 表示要交换的数，便可直接交换。

输出山峰个数：

所有交换操作完成后，我们可以遍历矩阵中的每一个元素并和上下左右比较，如果该元素为山峰，将答案加 1。

为了避免边角的山峰比较时越界，我们在读入时下标从 1 开始，并将矩阵初始化：memset(a,0,sizeof(a))。同时，存放矩阵的数组的大小应当大于等于

**输出山峰坐标**： 因为是先输出山峰个数再输出山峰坐标，所以我们不能得到一个输出一个，可以定义一个结构体 `Ans` 来存储答案，其中包括 `x,y` 即山峰坐标，即 `Ans[++ans].x=i; Ans[++ans].y=j`。 *** 至此，整道题目就完成了。 **注意事项**： - 若使用 `std::cin` 读入数据，请务必关闭同步流降低超出时间限制的风险； - 下标从 $1$ 开始，更加符合实际意义且方便进行比较； ## 视频题解 完整代码见视频题解 ![](bilibili:BV1qW4y1t7Fk?page=6)