计算网格中标记节点 k 距离内的节点

Question

我正在尝试解决编码挑战，但我的解决方案性能不佳，我正在寻求有关如何改进算法的意见或建议。

拼图如下：

You are given a grid of cells that represents an orchard, each cell can be either an empty spot (0) or a fruit tree (1). A farmer wishes to know how many empty spots there are within the orchard that are within k distance from all fruit trees.

距离使用taxicab geometry计算，例如：

k = 1

[1, 0]
[0, 0]

the answer is 2 as only the bottom right spot is >k distance from all trees.

我的解决方案是这样的：

遍历网格并存储所有树位置
从第一个树位置开始 BFS 并存储所有空点，直到我们到达超过 k 距离的邻居
从下一个树位置开始BFS并存储空点的交集
重复第 3 步，直到我们遍历所有树位置
Return所有路口后剩余的空位数

我发现对于具有大 k 值的大网格，我的算法变得非常慢，因为我最终要多次检查网格中的每个点。在做了一些研究之后，我发现了一些类似问题的解决方案，建议取两个最极端的目标节点，然后只比较与它们的距离：

但是，鉴于以下某些输入，这对我的挑战不起作用：

k = 4

[0, 0, 0, 1]
[0, 1, 0, 0]
[0, 0, 0, 0]
[1, 0, 0, 0]
[0, 0, 0, 0]

使用极端节点方法，即使距离中间树 5 距离，右下角的空白点也会被计算在内。

谁能指出我更有效的方法？我对这些类型的问题仍然很陌生，所以我发现很难看到我应该采取的下一步。

Answer 1

这不容易实现，但在许多情况下可能是次线性的，最多是线性的。考虑将每棵树的周长表示为四个角（它们标记一个旋转 45 度的正方形）。对于每棵树，计算它与当前交点的周界交点。困难在于管理交叉路口的拐角，由于对角线对齐，交叉路口可能包含多个点。运行在最后一个交叉路口内计算其中有多少空位。

Answer 2

由于您使用的是出租车距离，因此不需要 BFS。您可以直接计算空地和树之间的距离。

此算法基于 https://whosebug.com/users/3080723/stef

的建议

// select tree near top left corner
SET flag false
LOOP r over rows
  LOOP c over columns
     IF tree at c, r
         SET t to tree at c,r
         SET flag true
         BREAK
  IF flag
     BREAK   
LOOP s over empty spots
  Calculate distance between s and t
  IF distance <= k
     ADD s to spotlist
LOOP s over spotlist
  LOOP t over trees, starting at bottom right corner
     Calculate distance between s and t
     IF distance > k
         REMOVE s from spotlist
         BREAK
RETURN spotlist

Answer 3

由于网格和距离结构，此问题有一个简单的线性时间解决方案。给定一棵坐标为 (a, b) 的果树，考虑 4 条对角线包围它周围距离为 k 的盒子。向下和向右的对角线具有常数值 x + y，而向下和向左的对角线具有常数值 x - y。

点 (x, y) 在框内（因此，在 (a, b) 的距离 k 内）当且仅当：

a + b - k <= x + y <= a + b + k，并且
a - b - k <= x - y <= a - b + k

所以我们可以遍历我们的果树 (a, b) 来找到四个数字：

first_max = max(a + b - k); first_min = min(a + b + k);
second_max = 最大值(a - b - k); second_min = min(a - b + k);

其中 min 和 max 接管所有果树。然后，遍历空单元格（或者做一些数学运算并减去果树数量，如果你的网格很大），计算有多少空点 (x,y) 满足

first_max <= x + y <= first_min，并且
second_max <= x - y <= second_min.

此 Python 代码（以程序风格编写）说明了这一想法。每个边界框的每条对角线恰好截断了平面的一半，所以这相当于平行半平面的交集：

fruit_trees = [(a, b) for a in range(len(grid))
                      for b in range(len(grid[0]))
                      if grid[a][b] == 1]

northwest_half_plane = -infinity
southeast_half_plane = infinity

southwest_half_plane = -infinity
northeast_half_plane = infinity

for a, b in fruit_trees:
    northwest_half_plane = max(northwest_half_plane, a - b - k)
    southeast_half_plane = min(southeast_half_plane, a - b + k)

    southwest_half_plane = max(southwest_half_plane, a + b - k)
    northeast_half_plane = min(northeast_half_plane, a + b + k)

count = 0
for x in range(len(grid)):
    for y in range(len(grid[0])):
        if grid[x][y] == 0:
            if (northwest_half_plane <= x - y <= southeast_half_plane
            and southwest_half_plane <= x + y <= northeast_half_plane):
                count += 1

print(count)

关于代码的一些注释：从技术上讲，数组坐标是从图片的笛卡尔坐标旋转四分之一圈，但这在这里并不重要。代码故意遗漏某些看似显而易见的 'optimizations'，原因有二：1. 最佳优化取决于果树和网格的输入格式，以及 2. 解决方案，虽然概念简单并且易于阅读，但在编写时却不容易正确，重要的是代码必须 'obviously correct'。 'exit early and return 0 if a lower bound exceeds an upper bound'之类的东西以后如果需要性能可以加上。

Answer 4

正如 @kcsquared 所回答，在 JAVA

中提供了一个实现

public int solutionGrid(int K, int [][]A){
    int m=A.length;
    int n=A[0].length;
    int k=K;

    //to store the house coordinates
    Set<String> houses=new HashSet<>();

    //Find the house and store the coordinates
    for(int i=0;i<m;i++) {
        for (int j = 0; j < n; j++) {
            if (A[i][j] == 1) {
                houses.add(i + "&" + j);
            }
        }
    }
    int northwest_half_plane =  Integer.MIN_VALUE;
    int southeast_half_plane =  Integer.MAX_VALUE;

    int southwest_half_plane = Integer.MIN_VALUE;
    int northeast_half_plane = Integer.MAX_VALUE;

    for(String ele:houses){
        String arr[]=ele.split("&");
        int a=Integer.valueOf(arr[0]);
        int b=Integer.valueOf(arr[1]);
        northwest_half_plane = Math.max(northwest_half_plane, a - b - k);
        southeast_half_plane = Math.min(southeast_half_plane, a - b + k);

        southwest_half_plane = Math.max(southwest_half_plane, a + b - k);
        northeast_half_plane = Math.min(northeast_half_plane, a + b + k);
    }
    int count = 0;
    for(int x=0;x<m;x++) {
        for (int y = 0; y < n; y++) {
            if (A[x][y] == 0){
                if ((northwest_half_plane <= x - y &&  x - y <= southeast_half_plane)
                && southwest_half_plane <= x + y &&  x + y <= northeast_half_plane){
                    count += 1;
                }

            }
        }
    }
    return count;
}

计算网格中标记节点 k 距离内的节点

Count nodes within k distance of marked nodes in grid

algorithm

optimization

graph-theory

graph-algorithm