给定像元中2D数组中最近的检查点像元

Question

我得到了一个M X N矩阵，其中c个单元是标记为check2points。此外，我得到了p个其他单元格（我们将这些其他单元格的集合称为T）。如何找到从T中的像元到最近的距离检查点单元格（我需要找到T中每个单元格的距离）？

M，N，c，p <= 5 *（10 ^ 5）

注意：我只能在一个单元格的右，左，上和下移动。距离这里表示曼哈顿距离或$ \ ell1 $范数定义为：Dist（（x_1，y_1），（x_2，y_2））= ||（x_1，y_1）-（x_2，y_2）|| =| x_1-y_1 | + | x_2-y_2 |

我尝试了平凡的O（c * p）方法，在该方法中，我找到了从T中的一个单元到所有检查点单元的最小曼哈顿距离（并对T中的每个单元重复了此过程）。但是在某些测试案例中，它提供了TLE（2.08s）。

#include <iostream>

using namespace std;

long long int ManhattanDistance(long long int x, long long int y, long long int pit_x[], long long int pit_y[], long long int h){

    long long int temp, min;
    for(long long int j = 0; j < h; ++j){
        temp = abs(x-pit_x[j]) + abs(y-pit_y[j]);
        if(j == 0)
            min = temp;
        else{
            if(temp < min){
                min = temp;
            }
        }
    }
    return min;
}

int main(void){

    long long int n, m, h, p;
    cin >> n >> m >> h >> p;
    long long int pit_x[h], pit_y[h], person_x[p], person_y[p], manhattan[p];
    for(long long int i = 0; i < h; ++i){
        cin >> pit_x[i] >> pit_y[i];
    }
    for(long long int i = 0; i < p; ++i){
        cin >> person_x[i] >> person_y[i];
    }
    for(long long int i = 0; i < p; ++i){
        manhattan[i] = ManhattanDistance(person_x[i], person_y[i], pit_x, pit_y, h);
        cout << manhattan[i] << "\n";
    }


    return 0;
}

我该如何优化？

我曾考虑过进行多源广度优先搜索，但是再次是$ O（M * N）$，它的复杂度比上面的代码大。

[请帮助我进行优化。

Answer 1

似乎矩阵结构不会影响搜索（我们不能在某些屏障单元上停止，依此类推）。在这种情况下，您可以将检查点视为具有其坐标的点云，因此值得利用一些空间数据结构。

我建议对曼哈顿度量标准使用k-d tree。它们旨在查询对数时间中最近的邻居。因此，您可以在O(C logC)中构建kd-tree并在O(P logC)中进行查询。

P.S。在kd-tree中使用Manhattan范数为quite possible，这是一个任意示例-scipy kd-tree具有参数Which Minkowski p-norm to use. 1 is the sum-of-absolute-values “Manhattan” distance，nanoflann C ++库L1 (Manhattan)。毫无疑问，确实存在一些简短而简单的kd-tree实现。