题目内容

有一幅大小为 $w \times h$ 的二维图像，图像中每个位置都记录了一个整数亮度值。令坐标 $(x,y)$ 表示图像中的位置，其中 $x$ 是列编号，取值范围为 0 到 $w-1$；$y$ 是行编号，取值范围为 0 到 $h-1$。图像宽度 $w$ 和高度 $h$ 均为奇数，因此图像中心坐标定义为

对于图像中的任意坐标 $(x,y)$，它到图像中心 $c=(c_x,c_y)$ 的距离采用曼哈顿距离：

现在给定一个目标亮度值 $m$，请在所有亮度等于 $m$ 的坐标中，按照以下规则排序：

• 先按 $D(x,y)$ 从小到大排序；
• 如果 $D(x,y)$ 相同，则按 $x$ 从小到大排序；
• 如果 $x$ 也相同，则按 $y$ 从小到大排序。

最终需要输出排序后的前 $k$ 个坐标。如果亮度等于 $m$ 的坐标数量不足 $k$ 个，则输出全部符合条件的坐标。

约束条件

• $w$ 和 $h$ 均为奇数，取值范围为 1 到 2000。
• $m$ 的取值范围为 1 到 1000。
• $k$ 的取值范围为 1 到 100，且 $k \le w \times h$。
• 图像中每个亮度值的取值范围为 1 到 1000。
• 图像中至少存在一个亮度等于 $m$ 的坐标。

输入描述

第一行包含两个整数 $w$ 和 $h$，以空格分隔，依次表示图像宽度和图像高度。

第二行包含一个整数 $m$，表示目标亮度值。

第三行包含一个整数 $k$，表示需要输出的坐标数量。

接下来的 $h$ 行，每行包含 $w$ 个整数，以空格分隔，按行顺序给出图像中每个位置的亮度值。

输出描述

输出一行，包含结果坐标序列。每个坐标输出两个整数 $x$ 和 $y$，先输出 $x$ 再输出 $y$，两个整数之间用一个空格分隔；相邻坐标之间也用一个空格分隔。如果符合条件的坐标数量不足 $k$ 个，则输出全部符合条件的坐标。

样例1

输入

1 1
7
1
7

输出

0 0

说明

图像宽度为 1、高度为 1，中心坐标为 $(0,0)$。

图像中唯一位置 $(0,0)$ 的亮度为 7，等于目标亮度 7。

该位置到中心的距离为 $D(0,0)=|0-0|+|0-0|=0$。

因此输出前 1 个坐标为 $(0,0)$，即 0 0。

样例2

输入

5 3
9
4
9 1 1 1 9
1 1 9 1 1
1 9 1 9 1

输出

2 1 1 2 3 2 0 0

说明

图像宽度为 5、高度为 3，中心坐标为 $(2,1)$。

亮度等于 9 的坐标有 $(0,0)$、$(4,0)$、$(2,1)$、$(1,2)$、$(3,2)$。

分别计算曼哈顿距离：

$(2,1)$：$D=|2-2|+|1-1|=0$

$(1,2)$：$D=|1-2|+|2-1|=2$

$(3,2)$：$D=|3-2|+|2-1|=2$

$(0,0)$：$D=|0-2|+|0-1|=3$

$(4,0)$：$D=|4-2|+|0-1|=3$

排序后前 4 个坐标为 $(2,1)$、$(1,2)$、$(3,2)$、$(0,0)$，输出为 2 1 1 2 3 2 0 0。

样例3

输入

7 5
4
5
1 1 1 1 1 1 1
1 1 1 4 1 1 1
1 1 4 4 4 1 1
1 1 1 4 1 1 1
1 1 1 1 1 1 1

输出

3 2 2 2 3 1 3 3 4 2

说明

图像宽度为 7、高度为 5，中心坐标为 $(3,2)$。

亮度等于 4 的坐标有 $(3,1)$、$(2,2)$、$(3,2)$、$(4,2)$、$(3,3)$。

分别计算曼哈顿距离：

$(3,2)$：$D=|3-3|+|2-2|=0$

$(2,2)$：$D=|2-3|+|2-2|=1$

$(3,1)$：$D=|3-3|+|1-2|=1$

$(3,3)$：$D=|3-3|+|3-2|=1$

$(4,2)$：$D=|4-3|+|2-2|=1$

排序时先按距离从小到大排列，距离为 1 的坐标再按 $x$ 从小到大排列，其中 $x=3$ 的两个坐标按 $y$ 从小到大排列。

最终前 5 个坐标为 $(3,2)$、$(2,2)$、$(3,1)$、$(3,3)$、$(4,2)$，输出为 3 2 2 2 3 1 3 3 4 2。

样例4

输入

3 5
6
4
1 1 1
1 1 1
6 1 1
1 1 1
1 1 6

输出

0 2 2 4

说明

图像宽度为 3、高度为 5，中心坐标为 $(1,2)$。

亮度等于 6 的坐标只有 $(0,2)$ 和 $(2,4)$。

分别计算曼哈顿距离：

$(0,2)$：$D=|0-1|+|2-2|=1$

$(2,4)$：$D=|2-1|+|4-2|=3$

排序后的坐标为 $(0,2)$、$(2,4)$。

虽然需要输出前 4 个坐标，但符合条件的坐标只有 2 个，因此输出全部，即 0 2 2 4。

开通会员即可查看完整视频题解：1.题目讲解 2.思路分析 3.逐行代码手写