计算网格中标记节点 k 距离内的节点 [英] Count nodes within k distance of marked nodes in grid

问题描述

我正在尝试解决编码挑战，但是我的解决方案不是很高效，我正在寻找有关如何改进算法的建议.

拼图如下:

<块引用>

您将获得一个代表果园的单元格网格，每个单元格可以是一个空点 (0) 或一棵果树 (1).一位农民想知道果园内距离所有果树 k 距离内有多少空位.

使用

这个 Python 代码(以程序风格编写)说明了这个想法.每个边界框的每条对角线都恰好截断了平面的一半，因此这相当于平行半平面的交集:

fruit_trees = [(a, b) for a in range(len(grid))对于范围内的 b(len(grid[0]))如果网格[a][b] == 1]Northwest_half_plane = -infinitySoutheast_half_plane = 无穷大Southwest_half_plane = -infinityNortheast_half_plane = 无穷大对于fruit_trees中的a，b: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)计数 = 0对于范围内的 x(len(grid)):对于范围内的 y(len(grid[0])):如果网格[x][y] == 0:如果(northwest_half_plane <= x - y <= southeast_half_plane和 Southwest_half_plane <= x + y <= northeast_half_plane):计数 += 1打印(计数)

关于代码的一些说明:从技术上讲，数组坐标是从图片的笛卡尔坐标旋转四分之一圈，但这在这里无关紧要.代码故意省略了某些看似显而易见的优化"，原因有二:1. 最佳优化取决于果树和网格的输入格式，以及 2. 解决方案，同时概念简单且简单阅读，在写作时要正确并不容易，重要的是代码明显正确".如果需要性能，可以稍后添加诸如如果下限超过上限则提前退出并返回 0"之类的内容.

I am attempting to solve a coding challenge however my solution is not very performant, I'm looking for advice or suggestions on how I can improve my algorithm.

The puzzle is as follows:

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.

Distance is counted using taxicab geometry, for example:

k = 1

[1, 0]
[0, 0]

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

My solution goes something like this:

1. loop over grid and store all tree positions
2. BFS from the first tree position and store all empty spots until we reach a neighbour that is beyond k distance
3. BFS from the next tree position and store the intersection of empty spots
4. Repeat step 3 until we have iterated over all tree positions
5. Return the number of empty spots remaining after all intersections

I have found that for large grids with large values of k, my algorithm becomes very slow as I end up checking every spot in the grid multiple times. After doing some research, I found some solutions for similar problems that suggest taking the two most extreme target nodes and then only comparing distance to them:

• https://www.codingninjas.com/codestudio/problem-details/count-nodes-within-k-distance_992849
• https://www.geeksforgeeks.org/count-nodes-within-k-distance-from-all-nodes-in-a-set/

However this does not work for my challenge given certain inputs like below:

k = 4

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

Using the extreme nodes approach, the bottom right empty spot is counted even though it is 5 distance away from the middle tree.

Could anyone point me towards a more efficient approach? I am still very new to these types of problems so I am finding it hard to see the next step I should take.

解决方案

There is a simple, linear time solution to this problem because of the grid and distance structure. Given a fruit tree with coordinates (a, b), consider the 4 diagonal lines bounding the box of distance k around it. The diagonals going down and to the right have a constant value of x + y, while the diagonals going down and to the left have a constant value of x - y.

A point (x, y) is inside the box (and therefore, within distance k of (a, b)) if and only if:

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

So we can iterate over our fruit trees (a, b) to find four numbers:

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

where min and max are taken over all fruit trees. Then, iterate over empty cells (or do some math and subtract fruit tree counts, if your grid is enormous), counting how many empty spots (x,y) satisfy

1. first_max <= x + y <= first_min, and
2. second_max <= x - y <= second_min.

This Python code (written in a procedural style) illustrates this idea. Each diagonal of each bounding box cuts off exactly half of the plane, so this is equivalent to intersection of parallel half planes:

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)

Some notes on the code: Technically the array coordinates are a quarter-turn rotated from the Cartesian coordinates of the picture, but that is immaterial here. The code is left deliberately bereft of certain 'optimizations' which may seem obvious, for two reasons: 1. The best optimization depends on the input format of fruit trees and the grid, and 2. The solution, while being simple in concept and simple to read, is not simple to get right while writing, and it's important that the code be 'obviously correct'. Things like 'exit early and return 0 if a lower bound exceeds an upper bound' can be added later if the performance is necessary.

这篇关于计算网格中标记节点 k 距离内的节点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！