题解

题面描述

给定一张二维图像，图像中每个值表示该坐标下的亮度。现在给定一个亮度值 $m$，请返回离图像中心坐标最近的 $k$ 个亮度为 $m$ 的坐标 $(x, y)$。

题解思路

1. 坐标系和中心坐标计算
   给定图像宽度 $w$ 和高度 $h$，图像的中心坐标为 $(\frac{w-1}{2}, \frac{h-1}{2})$，这是我们计算距离时的参考点。

题目内容

给定一张二维图像，图像中每个值表示该坐标下的亮度。现在给定一个亮度值 $m$ ，请返回离图像中心坐标最近的 $k$ 个亮度为 $m$ 值的坐标 $(x，y)$。

提示：

1.图像中元素的坐标范围 $x:[0,w-1]，y:[0,h-1]$ 。

2.图像宽高 $w,h$ 均为奇数，图像中心坐标 $(w-1)/2,(h-1)/2$ 。

3.平面上两点之间的距离为 $∣x_1-x_2∣+∣y_1-y_2∣$ 。

4.在距离相同的情况下，以 $x$ 小的点优先；当 $x$ 相同时，以 $y$ 小的点优先。

5.题目可保证至少存在一个亮度值为 $m$ 的点。

输入描述

第一行输入为图像宽度 $w$ 和图像高度 $h$，以空格隔开，宽高范围为 $1$~ $2000$

第二行输入为给定亮度值 $m$ ，范围为 $1$ ~ $1000$

第三行输入为需要输出的亮度值为 $m$ 的坐标个数 $k$ ，范围为 $1$ ~ $100$ ，且 $k <= w*h$

接下来共 $h$ 行，每行内为 $w$ 个亮度，以空格隔开，亮度范围为 $1$ ~ $1000$

输出描述

按顺序输出坐标序列，坐标 $x$ 和 $y$ 以空格隔开，坐标间使用空格隔开如样例所示。

$x,y$ 坐标均不相同时以 $x$ 增序排列， 坐标相同时以 $y$ 增序排列。若满足条件的坐标个数不足 $k$，则以实际坐标个数输出。

样例1

输入

5 5
10
3
10 2 3 4 5
1 2 3 4 10
1 2 3 10 5
1 10 3 4 5
1 2 3 4 5

输出

3 2 1 3 4 1

说明

该用例图像 $w=5，h=5$，给定亮度值 $m=10$ ，需要输出 $m = 10$ 的距离中心最近的 $3$ 个坐标。

该图像中心坐标为 $(2,2)$ 。

从图像中可以看出，距离中心坐标最近的 $m = 10$ 的坐标为 $(3,2)$ ，距离为 $∣3-2∣+∣2-2∣=1$ ;

距离第二近的坐标为 $(1,3)$ ，距离为 $∣1-2∣+∣3-2∣=2$ ;

距离第三近的坐标为 $(4,1)$ ，距离为 $∣4-2∣+∣1-2∣=3$ ;

由上可知，三个坐标为 $(3,2)、(1,3)、(4,1)$，按照输出格式要求，输出为 $3$ $2$ $1$ $3$ $4$ $1$

样例2

输入

3 3
10
6
1 10 1
10 10 10
1 10 1

输出

1 1 0 1 1 0 1 2 2 1

说明

该用例图像 $w =3，h=3$，给定亮度值 $m = 10$ ，需要输出 $m = 10$ 的距离中心最近的 $6$ 个坐标。

该图像中心坐标为 $(1,1)$ 。

从图像中可以看出，距离中心坐标最近的 $m= 10$ 的坐标为 $(1,1)$ ，距离为 $0$ ;

剩余满足 $m = 10$ 的坐标有 $4$ 个，分别为 $(1,0)(0,1)(2,1)(1,2)$，距离均为 $1$ .

由输出规则 $x ,y$ 坐标均不相同时以 $x$ 增序排列， $x$ 坐标相同时以 $y$ 增序排列，得到输出序列为 $(1,1)(0,1)(1,0)(1,2)(2,1)$，满足条件的坐标为 $5$ 个，不足输入中要求的 $6$ 个，实际只需输入 $5$ 个。

由上可知，输出为 $1$ $1$ $0$ $1$ $1$ $0$ $1$ $2$ $2$ $1$

提示

1.图像中元素的坐标范围 $x:[0,w -1],y:[0,h-1]$ 。

2.图像宽高 $w,h$ 均为奇数，图像中心坐标 $(w-1)/2,(h-1)/2$ 。

3.、平面上两点之间的距离为 $|x_1- x_2|+|y_1- y_2|$ 。

4.在距离相同的情况下，以 $x$ 小的点优先；当 $x$ 相同时，以 $y$ 小的点优先。