매트릭스

Question

에서 세포 이웃을 찾기 위해 어떻게 부울 값의 매트릭스 (5 × 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 

을, 나는 값이 true 가까이 셀을 찾을 필요가있다. 여기서 더 가깝다는 것은 더 낮은 이동 수로 도달 할 수있는 셀, 즉 행 차이와 열 차이의 합이 최소 인 셀이어야한다는 의미입니다. 따라서, 예를 들어 :

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

나는 알고리즘의 어떤 종류를 사용할 수 있습니까?

Answer 1

BFS - 즉각적인 이웃을 검색 한 다음 바로 인접한 각 이웃을 검색합니다. 각 단계에서 이전 단계의 단계보다 한 단계 앞선 셀을 검색합니다. 당신이 그 (것)들에게

Answer 2

를 반복하지 않도록 또한, 코드가 아래보십시오 세포가 이미 확인 된 추적 :

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