在一个环绕矩阵中查找相邻的单元格

Question

假设你有一个NxM维的矩阵。例如，一个4x4的矩阵：

0  1  2  3
4  5  6  7
8  9  10 11
12 13 14 15

每个单元格都有八个相邻的单元格。 例如，单元格5的相邻单元格包括：0、1、2、4、6、8、9、10。

0 1 2
4 5 6
8 9 10

但是，通过绕过矩阵也可以找到相邻的单元格，因此单元格7的相邻单元格为2、3、0、5、4、10、11、8。

2  3 | 0
6  7 | 4
10 11| 8

您可以同样地将其包裹在顶部和底部。

如果随机选择一个点(p)，是否有简单的方法来找到所有八个相邻单元格的值？ 到目前为止，我想出了这个列表，其中m是矩阵的宽度（在我们的例子中为4）。

adjacentcells = [p+1, p-1, p+m, p-m, p+m-1, p+m+1, p-m-1, p-m+1]
for value in adjacentcells:
    if value < 0:
        value = value + len(matrix)
    if value >= len(matrix)
        value = value % len(matrix)
    adjacentlist.append(value)

然而，当你选择角落中的一个单元格时，它会返回7个正确的相邻值和一个错误的单元格。有人能指出我的问题在哪里吗？

*由于某些复杂（愚蠢）原因，我将矩阵存储为字符串，这就是为什么我可以使用len(matrix)并得到16的原因。

- Miles Lincoln

---

m 代表什么？ - Code-Apprentice

此外，哪七个邻居被正确地找到了，哪一个没有？ - Code-Apprentice

@Code-Guru，m 是矩阵的宽度（n 是高度）。不正确的相邻方块取决于点 p 所在的边缘。 - Miles Lincoln

你能举出一两个例子来说明何时会出现错误的结果吗？ - Code-Apprentice

p==15产生的结果是[0, 14, 3, 11, 2, 4, 10, 12]，应该得到[0, 14, 3, 11, 2, 8, 10, 12]。 - Robᵩ

Answer 1

你需要在两个轴上分别使用模算术，而不仅仅是在计算的索引上使用。

尝试使用这个辅助函数：

def addr(x,y,m,n):
  """
  Given an MxN matrix stored in a 1-d sequence,
  return the index of (possibly wrapped) X,Y
  """
  return (y%n)*m+(x%m)

现在你可以计算相邻的单元格：

def getAdjacentCells(x,y):
  adjacentlist = []
  for dx in (-1, 0, +1):
    for dy in (-1, 0, +1):
      if(dx != 0 or dy != 0):
        adjacentlist.append(addr(x+dx, y+dy, 4, 4))
  return adjacentlist

而且，你可以证明它是有效的：

# 5
assert sorted(getAdjacentCells(1,1)) == [0,1,2,4,6,8,9,10]
# 7
assert sorted(getAdjacentCells(3,1)) == [0, 2, 3, 4, 6, 8, 10, 11]
# 15
assert sorted(getAdjacentCells(3,3)) == [0, 2, 3, 8, 10, 11, 12, 14]

- Robᵩ