在网格中，计算距离标记节点k个单位距离内的节点数。

Question

在网格中，计算距离标记节点k个单位距离内的节点数。

algorithmoptimizationgraph-theorygraph-algorithm

6

我正在尝试解决编程挑战，但我的解决方案效率不高，我正在寻求建议或建议，以改善我的算法。

谜题如下：

给定一个单元格网格，表示果园，每个单元格可以是空位（0）或果树（1）。农民希望知道果园中有多少空位距离所有果树的距离在k范围内。

使用曼哈顿几何计算距离，例如：

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，直到我们遍历完所有树的位置
返回所有交集后剩余的空位数目

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

然而，对于以下某些输入，此方法无法解决我的挑战：

k = 4

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

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

有没有人能指点我一个更有效的方法？我还很陌生这类问题，所以很难看到我应该采取的下一步。

- CaTs

“距离所有果树不超过k”这似乎很奇怪。如果果园是n x n的，且n > 2 * k，则没有任何一个位置可以距离所有树都不超过k。 - ravenspoint

@ravenspoint 果园可能很大，但也许只有少数树木，它们都靠得很近。如果两棵树的距离 > 2 * k，则无法在所有树上的任何点到达 k 的距离；这与 n > 2 * k 不等价。 - Stef

你能澄清一下你是指“所有树”还是“任何一棵树”吗？ - Richard

@Richard，“all trees”是正确的，请查看问题定义。 - CaTs

4个回答

2

由@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;
}

- Naveen Dhalaria

1

这可能不容易实现，但对于许多情况而言可以是次线性的，最多是线性的。考虑将每棵树的周长表示为四个角（它们标记了一个旋转45度的正方形）。对于每棵树，计算其周长与当前交集的交点。难点在于管理交集的角落，因为由于对角线的排列，它们可能包含多个点。在最终交集内运行以计算其中有多少空位。

- גלעד ברקן

0

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

该算法基于https://stackoverflow.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

- ravenspoint

这个解决方案与我最初的方案非常相似，但最后一个嵌套循环似乎真的会影响性能。我尝试使用BFS，因为我认为一旦到达>k距离的邻居，我可以节省时间终止搜索。 - CaTs

哎呀，当从spotlist中删除‘s’时，我忘记跳出树循环。这样做有助于提高性能。 - ravenspoint

第一次出现“计算s和t之间的距离”这行代码时，不清楚t指的是什么；它似乎没有被声明。 - גלעד ברקן

@גלעדברקן 这指的是将t设置为在c,r处的树。 - ravenspoint

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- kcsquared · Accepted Answer

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

如果点(x, y)在盒子内(因此，在距离k之内)，那么:

1. a + b - k <= x + y <= a + b + k 2. a - b - k <= x - y <= a - b + k

因此，我们可以遍历水果树(a, b)来找到四个数字:

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

其中min和max是针对所有水果树进行的。然后，遍历空单元格(或者通过一些数学方法减去水果树的数量，如果你的网格很大)，计算有多少个空位(x,y)满足:

1. first_max <= x + y <= first_min 2. 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)

关于代码的一些注释：从技术上讲，数组坐标与图片的笛卡尔坐标系相比旋转了四分之一圈，但这在此处并不重要。代码故意缺少某些“优化”，这些优化可能似乎很明显，原因有两个：1.最佳优化取决于水果树和网格的输入格式，2.解决方案虽然在概念上简单且易于阅读，但在编写时确保正确性并不容易，因此代码必须是“显然正确”的。如果需要性能，可以稍后添加像“如果下限超过上限，则提前退出并返回0”这样的内容。