如何在矩阵中找到单元格邻居

Question

我有一个5x5的布尔值矩阵：

matrix = [[False for x in range(5)] for x in range(5)]
matrix[0][3] = True
matrix[2][2] = True

F F F T F
F X F F F
F F T F F
F F F F F
F F F F F

给定一个索引，我需要找到离这个索引最近的值为True的单元格。这里的“最近”是指：到达这个单元格所需的移动次数最少，也就是说行和列的差值之和要最小。

举个例子：

row, column = find(row=1, column=1)
# row = 2
# column = 2

我可以使用什么样的算法呢？

Answer 1

试试下面的代码：

matrix = [[False for x in range(5)] for x in range(5)]
matrix[0][3] = True
matrix[2][2] = True

stack=[]


def find(rc):  # argument rc is a (row,col) tuple like (1,1). Don't pass it a 1,1 
    global stack
    r=rc[0] 
    c=rc[1]
    if (c+1 < 5) and (matrix[r][c+1]==True):
        print r,c+1
        stack=[]
        return
    if (c-1 > -1) and (matrix[r][c-1]==True):
        print r,c-1
        stack=[]
        return
    if (r+1 < 5) and (matrix[r+1][c]==True):
        print r+1,c
        stack=[]
        return
    if (r-1 > -1) and (matrix[r-1][c]==True):
        print r-1,c
        stack=[]
        return
    if r+1 < 5: stack.append((r+1,c))
    if r-1 > -1: stack.append((r-1,c))
    if c+1 < 5: stack.append((r,c+1))
    if c-1 > -1: stack.append((r,c-1))
    find(stack.pop(0))

>>> find((1,1))
2 2
>>> find((0,0))
0 3
>>> find((4,0))
2 2
>>> find((4,4))
2 2
>>> find((0,4)) 
0 3

Answer 2

广度优先搜索（BFS）是一种查找方法。它的工作方式是先查看你周围的邻居，然后再查看这些邻居的邻居，依此类推。每一步你都会检查比上一步更远的地方。同时，要记得记录哪些地方已经检查过了，这样就不会重复检查了。