SP1966 SKIVALL - Ski Valley

新罕布什尔州体育协会计划在白山地区建造一个前所未有的滑雪谷。这条滑雪道设计为先下坡再上坡，滑雪者可以凭借前半段下坡获得的速度，成功爬上后半段的上坡。为了增加游客的乐趣，他们希望寻找一条最长的这种滑雪路径。 为简化计算，他们将山地地形近似为一个方形区域组成的矩阵，并从新罕布什尔地理研究所获取每个区域的高度。滑雪谷是一串相邻的区域序列，这些区域的高度从起点开始一直下降，直到某个最低点，然后再从此开始上升。在整个滑雪谷的路径中，每个区域只能出现一次。两个区域相邻，当且仅当它们共享一条边。滑雪谷的长度定义为序列中区域的数量。 具体来说，地形是一个 $M \times N$ 的矩阵，其中 $(i, j)$ 表示第 $i$ 行第 $j$ 列的区域，$h(i, j)$ 表示该区域的高度。滑雪谷是一个序列 $(x_1, y_1), (x_2, y_2), \ldots, (x_l, y_l)$，该序列需满足以下条件： 1. 对于任意 $i$ ($1 \le i \le l-1$)，要么 $x_i = x_{i+1}$ 且 $|y_i - y_{i+1}| = 1$，要么 $y_i = y_{i+1}$ 且 $|x_i - x_{i+1}| = 1$（相邻规则）。 2. 如果 $i \neq j$ ($1 \le i, j \le l$)，则 $x_i \neq x_j$ 或 $y_i \neq y_j$（无重复规则）。 3. 存在一个 $k$ ($1 \le k \le l$)，使得 $h(x_1, y_1) > h(x_2, y_2) > \ldots > h(x_{k-1}, y_{k-1}) > h(x_k, y_k) < h(x_{k+1}, y_{k+1}) < \ldots < h(x_l, y_l)$（下坡-上坡规则）。 你的任务是编写一个程序，寻找最长的滑雪谷。如果有多个具有相同最大长度的滑雪谷，你可以任选其一。 注意：虽然他们并未特别限制滑雪谷必须两段的下坡和上坡，但你只需严格按规格实现即可。

第一行输入两个整数 $M$ 和 $N$ ($1 \le M, N \le 60$)，表示矩阵的行数和列数，中间用空格隔开。接下来 $M$ 行，每行包含 $N$ 个整数，第 $i$ 行的第 $j$ 个数表示 $h(i, j)$，范围在 $-10^6$ 到 $10^6$ 之间。矩阵中任意两个区域的高度均不相同。每行中的数字间用空格隔开。

输出的第一行为一个整数 $l_{\text{max}}$，表示最长滑雪谷的长度。接下来的 $l_{\text{max}}$ 行描述任一长度为 $l_{\text{max}}$ 的滑雪谷。每行包含两个整数，用空格隔开，每行第 $i$ 个数分别为 $x_i$ 和 $y_i$，表示滑雪谷中第 $i$ 个区域的坐标 $(x_i, y_i)$。

- $1 \le M, N \le 60$ - $-10^6 \le h(i, j) \le 10^6$ - 矩阵中任意两个区域的高度均不同。 **本翻译由 AI 自动生成**