如何在矩阵中找到单元邻域

Question

5个布尔值矩阵：

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

给定一个索引，我需要找到值为真的更接近的单元格。 其中closer意味着：移动次数越少可以到达的单元格，即行差和列差之和必须最小。 例如：

^{pr2}$

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

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-搜索近邻，然后搜索每个近邻的近邻，依此类推。。。在每个这样的步骤中，您将搜索比上一步更进一步的单元格。 此外，还要跟踪哪些单元格已经被检查过，这样就不会重复它们了