计算与矩阵中另一个单元格具有给定曼哈顿距离的单元格的数量
Count the number of cells with a given Manhattan distance from another cell in a matrix
我们有一个矩阵 A
,包含 M
行和 N
列,以及一个单元格 (X, Y)
。我们需要找到距离 (X, Y)
小于或等于 K
.
的曼哈顿距离 A
中的单元格数
示例:在下面的矩阵中,M = 6
、N = 7
、X = 4
、Y = 3
、K = 4
。答案是32
。
我可以从 (X, Y)
开始进行 BFS,并在找到具有给定距离的所有单元格后停止。但是矩阵可能非常庞大,所以我需要一个更好的解决方案。你能帮我吗?谢谢!
我在发布问题后~3 天解决了问题,但我没有时间在这里回答。由于我最近在我的博客上写了一篇关于解决这个问题的文章,所以我将 link 放在这里:solution
我们有一个矩阵 A
,包含 M
行和 N
列,以及一个单元格 (X, Y)
。我们需要找到距离 (X, Y)
小于或等于 K
.
A
中的单元格数
示例:在下面的矩阵中,M = 6
、N = 7
、X = 4
、Y = 3
、K = 4
。答案是32
。
我可以从 (X, Y)
开始进行 BFS,并在找到具有给定距离的所有单元格后停止。但是矩阵可能非常庞大,所以我需要一个更好的解决方案。你能帮我吗?谢谢!
我在发布问题后~3 天解决了问题,但我没有时间在这里回答。由于我最近在我的博客上写了一篇关于解决这个问题的文章,所以我将 link 放在这里:solution