在NxN板中查找与给定索引相邻的所有索引

Question

假设我有一个10x10电池板。每个单元格的索引从1到100（基于1的索引）。电路板是一个单元格列表：[1, 2, 3, ..., 100]。你知道吗

任务。给定一个单元格的索引，找到覆盖它的所有单元格。你知道吗

例如：

1 | 2 | 3 | 4
_____________
5 | 6 | 7 | 8
_____________
9 |10 |11 |12
_____________
13|14 |15 |16

给定索引：11

返回：[6, 7, 8, 12, 16, 15, 14, 10]，顺序不重要。你知道吗

我的解决方案是：

def allAdjacentCell(given_index):
    result = []
    dimension = 4 # length of a line
    if (1 <= given_index - dimension <= 16):
        result.append(given_index - 1) # the cell above the given cell
    if (1 <= given_index + dimension <= 16):
        # below given index
    if (1 <= given_index - 1 <= 16):
        # ...
    if (1 <= given_index + 1 <= 16):
        # ...
    # check for diagonal cells
    return result

如果给定的单元格位于电路板中心的某个位置，我的方法似乎返回了正确的结果。但如果给定的单元格位于角或边上，则是错误的。例如，如果给定cell=5，那么该方法将包括索引4处的单元格，尽管它与5不相邻。你知道吗

解决这个问题的正确方法是什么？你知道吗

Answer 1

我们注意到，只有当索引值位于最右边或最左边的列或最上面或最下面的行中时，才会得到“rougue”值。你知道吗

顶行/底行rogue值仅为负值或越界值。你知道吗

对于最左侧列中的索引，rogue值将具有%dim=0。你知道吗

对于最右边列中的索引，rogue值将具有%dim=1。你知道吗

因此，我们只需要从中心索引的标准值中过滤掉它们。你知道吗

def all_adjacent(index,dim):
    arr = [index+1,index-1,index+dim,index-dim,index+dim+1,index+dim-1,index-dim+1,index-dim-1]
    if index%dim==0: ## right most row
         arr = filter(lambda x:x%dim!=1,arr)
    if index%dim==1: ## left most  row
        arr = filter(lambda x:x%dim!=0,arr)

    arr = filter(lambda x:x>=1 and x<=dim*dim,arr)  ## top and bottom rows

    return arr

Answer 2

Willem Van Onsem给出的答案的一个更普通的版本，其中我显式地在索引和更容易处理的坐标之间转换。我还包括一个测试，检查是否一切都按预期进行：

dimension = 4

def label_to_coords(label):
    x = (label - 1) % dimension
    y = (label - 1 - x) // dimension
    return x, y

def coords_to_label(x, y):
    return x + dimension * y + 1


def allAdjacentCell(given_index):
    result = []
    x, y = label_to_coords(given_index)
    for delta_x in range(-1, 2):
        for delta_y in range(-1, 2):
            if not (delta_x == delta_y == 0):
                new_x = x + delta_x
                new_y = y + delta_y
                if (0 <= new_x < dimension) and (0 <= new_y < dimension):
                    result.append(coords_to_label(new_x, new_y))
    return result

def test():
    size = dimension**2
    for i in range(1, size + 1):
        print(i, allAdjacentCell(i))

if __name__ == "__main__":
    test()

Answer 3

问题是，如果它是一个边情况（例如5），那么5-1仍然是一个有效的索引（但不是相邻的索引）。您可以通过首先确定x和y来解决这个问题：

x = (given_index-1) % dimension
y = (given_index-1) // dimension

没有必要这么难：您知道结果应该在0（包含）和15（包含）之间。可以使用嵌套的for循环：

result = []
for nx in (x-1,x,x+1):
    if 0 <= nx < dimension:
        for ny in (y-1,y,y+1):
            if 0 <= ny < dimension and (nx != x or ny != y):
                result.append(ny*dimension+nx+1)

你甚至可以把它放在一个漂亮的内衬里：

x = (given_index-1) % dimension
y = (given_index-1) // dimension
result = [ny*dimension+nx+1 for nx in (x-1,x,x+1) if 0 <= nx < dimension for ny in (y-1,y,y+1) if 0 <= ny < dimension and (nx != x or ny != y)]