gpt4 book ai didi

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

转载 作者:行者123 更新时间:2023-12-04 11:49:51 27 4
gpt4 key购买 nike

我正在尝试解决编码挑战,但是我的解决方案不是很高效,我正在寻找有关如何改进算法的建议或建议。
谜底如下:

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,直到我们遍历了所有树位置
  • 返回所有交叉点后剩余的空位数

  • 我发现对于具有大 k 值的大网格,我的算法变得非常慢,因为我最终会多次检查网格中的每个点。在做了一些研究之后,我找到了一些类似问题的解决方案,建议采用两个最极端的目标节点,然后只比较它们的距离:
  • 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/

  • 但是,鉴于以下某些输入,这对我的挑战不起作用:
    k = 4

    [0, 0, 0, 1]
    [0, 1, 0, 0]
    [0, 0, 0, 0]
    [1, 0, 0, 0]
    [0, 0, 0, 0]
    使用极端节点方法,即使距离中间树 5 距离,也会计算右下角的空点。
    有人能指出我更有效的方法吗?我对这些类型的问题仍然很陌生,所以我发现很难看到我应该采取的下一步。

    最佳答案

    由于网格和距离结构,这个问题有一个简单的线性时间解决方案。给定坐标为 (a, b) 的果树,考虑围绕它的距离为 k 的框的 4 条对角线。向下和向右的对角线具有恒定的 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 = 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。

  • Bounding box inequalities
    这个 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”之类的内容。

    关于algorithm - 计算网格中标记节点 k 距离内的节点,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/69075779/

    27 4 0
    Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
    广告合作:1813099741@qq.com 6ren.com