题解

题面描述

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

题解思路

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

2. 遍历图像并找到亮度为 $m$ 的点
   对于每个点 $(x, y)$，如果该点的亮度值为 $m$，则计算它与中心点的曼哈顿距离：

   $$d = |x - \frac{w-1}{2}| + |y - \frac{h-1}{2}|$$

3. 排序和选择
   将所有亮度为 $m$ 的点按距离中心的曼哈顿距离排序。若距离相同，则按 $x$ 坐标排序，若 $x$ 相同，再按 $y$ 坐标排序。最后，选择距离最小的 $k$ 个点。

4. 输出结果
   输出排序后的前 $k$ 个坐标。

cpp

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);  // 加速输入输出
    cin.tie(nullptr);  // 解绑 cin 和 cout，进一步加速输入输出

    int w, h, m, k;
    cin >> w >> h;  // 输入图像的宽度和高度
    cin >> m;  // 输入目标亮度值
    cin >> k;  // 输入需要输出的坐标个数
    
    int cx = (w - 1) / 2, cy = (h - 1) / 2;  // 计算图像中心坐标
    
    vector<tuple<int, int, int>> v;  // 存储亮度为 m 的点（距离，x，y）
    v.reserve(w * (long long)h);  // 预先分配足够的空间，避免频繁扩容
    
    // 遍历图像的每个点
    for (int y = 0; y < h; y++) {
        for (int x = 0; x < w; x++) {
            int b;
            cin >> b;  // 读取每个点的亮度值
            
            if (b == m) {  // 如果亮度值等于 m
                int d = abs(x - cx) + abs(y - cy);  // 计算该点到中心的曼哈顿距离
                v.emplace_back(d, x, y);  // 存储（距离，x，y）元组
            }
        }
    }
    
    int n = v.size(), t = min(k, n);  // 选择前 k 个点，若亮度为 m 的点少于 k 个，取实际数量
    
    // 自定义排序函数：首先按距离排序，其次按 x 坐标排序，最后按 y 坐标排序
    auto cmp = [](auto &a, auto &b) {
        if (get<0>(a) != get<0>(b)) return get<0>(a) < get<0>(b);  // 按距离排序
        if (get<1>(a) != get<1>(b)) return get<1>(a) < get<1>(b);  // 若距离相同，按 x 坐标排序
        return get<2>(a) < get<2>(b);  // 若距离和 x 坐标都相同，按 y 坐标排序
    };

    // 对亮度为 m 的点按距离、x、y 排序
    if (n > t) 
        partial_sort(v.begin(), v.begin() + t, v.end(), cmp);  // 如果有多于 k 个点，部分排序
    else 
        sort(v.begin(), v.end(), cmp);  // 否则对所有点进行排序

    // 输出结果，按照排序后的前 t 个点
    for (int i = 0; i < t; i++) {
        if (i) cout << ' ';  // 在每对坐标之间加空格
        cout << get<1>(v[i]) << ' ' << get<2>(v[i]);  // 输出每个坐标的 x 和 y
    }

    return 0;
}

Python

import sys

def main():
    # 读取输入数据
    data = sys.stdin.read().split()
    it = iter(data)
    
    # 图像的宽度、高度和亮度值
    w = int(next(it))
    h = int(next(it))
    m = int(next(it))
    k = int(next(it))
    
    # 计算图像中心坐标
    cx = (w - 1) // 2
    cy = (h - 1) // 2
    
    # 存储亮度为 m 的点和其距离
    pts = []
    
    # 遍历图像的每个点
    for y in range(h):
        for x in range(w):
            b = int(next(it))
            # 如果亮度值等于 m，则计算距离
            if b == m:
                d = abs(x - cx) + abs(y - cy)
                pts.append((d, x, y))
    
    # 按照（距离，x，y）排序
    pts.sort()
    
    # 输出结果，选择前 k 个坐标
    res = pts[:min(k, len(pts))]
    out = []
    for _, x, y in res:
        out.append(f"{x} {y}")
    sys.stdout.write(" ".join(out))

if __name__ == "__main__":
    main()

Java

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        // 读取输入数据
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        // 图像的宽度、高度和亮度值
        int w = Integer.parseInt(st.nextToken());
        int h = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(br.readLine().trim());
        int k = Integer.parseInt(br.readLine().trim());
        
        // 计算图像中心坐标
        int cx = (w - 1) / 2;
        int cy = (h - 1) / 2;
        
        // 存储亮度为 m 的点和其距离
        List<int[]> pts = new ArrayList<>();
        
        // 遍历图像的每个点
        for (int y = 0; y < h; y++) {
            st = new StringTokenizer(br.readLine());
            for (int x = 0; x < w; x++) {
                int b = Integer.parseInt(st.nextToken());
                // 如果亮度值等于 m，则计算距离
                if (b == m) {
                    int d = Math.abs(x - cx) + Math.abs(y - cy);
                    pts.add(new int[]{d, x, y});
                }
            }
        }
        
        // 按照（距离，x，y）排序
        pts.sort(Comparator
            .comparingInt((int[] a) -> a[0])
            .thenComparingInt(a -> a[1])
            .thenComparingInt(a -> a[2])
        );
        
        // 输出结果，选择前 k 个坐标
        StringBuilder sb = new StringBuilder();
        int t = Math.min(k, pts.size());
        for (int i = 0; i < t; i++) {
            int[] p = pts.get(i);
            if (i > 0) sb.append(' ');
            sb.append(p[1]).append(' ').append(p[2]);
        }
        System.out.print(sb.toString());
    }
}

题目内容

给定一张二维图像，图像中每个值表示该坐标下的亮度。现在给定一个亮度值 $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$ 小的点优先。