최단 경로 알고리즘 - 액세스 할 수없는 셀이있는 행렬

Question

인터뷰에서이 질문을 받았습니다. 어떻게해야할지 모르겠다. 기본적으로 부울 행렬이 있습니다. 0은 셀에 액세스 할 수 없음을 나타냅니다. 주어진 출발점과 목적지 셀을 감안할 때, 접근 할 수없는 셀에서 호핑하지 않고 시작부터 목적지까지 최단 경로를 어떻게 구성합니까? 네 방향으로 모두 여행 할 수 있습니다.

감사합니다.

Answer 1

빵 우선 검색을 사용해야합니다. 이 직사각형 보드에서 그래프를 변조하십시오.

주요 아이디어 :

Distance to start cell = 0 

Previous cell for start = some not existed cell 

Add start cell to queue 

Mark start cell as visited 

While queue is not empty 

    Take off cell Y from queue, if cell Y equal to finish cell, exit 

    Check all possible moves from it (goes Up, Down, Left, Right, except "walls") 

    For every possible cell adjancent from Y 
      Check that possible cell X is not visited before 
       If Yes, mark X as visited and add to queue 
       Distance to cell X = distance to cell Y + 1 
       Previous cell in shortest path to cell X = Y 

그 후, 당신은 쉽게 이전 배열에 마무리 세포에서 이동, 최단 경로를 얻을 수 있습니다.

자세한 내용은 - 위키 백과을 확인 - https://en.wikipedia.org/wiki/Breadth-first_search

Answer 2

을 간단한 너비 우선 검색이 문제를 해결하기에 충분하다. 다음은 Python에서 구현 된 샘플입니다.

를 Input.txt이

4 4 
1 1 4 4 
1 1 0 0 
0 1 0 0 
0 1 1 0 
0 0 1 1 

솔루션 :

import sys 
from collections import deque 
sys.stdin = open ("Input.txt", "r") 
Table = [] 
Queue = deque() 
Visited = set() 

n, m = [int (i) for i in sys.stdin.readline().split()] 
startx, starty, endx, endy = [int(i)-1 for i in sys.stdin.readline().split()] 
for j in xrange(n): Table.append ([int (i) for i in sys.stdin.readline().split()]) 

if Table[startx][starty] == 0: 
    print 0 
    sys.exit(0) 

def process (X, Y, Dist): 
    if (X == endx and Y == endy): 
     print Dist + 1 
     sys.exit(0) 
    if X + 1 != m and Table[X + 1][Y] and (X + 1, Y) not in Visited: 
     Queue.append ((X + 1, Y, Dist + 1)) 
    if Y + 1 != n and Table[X][Y + 1] and (X, Y + 1) not in Visited: 
     Queue.append ((X, Y + 1, Dist + 1)) 
    if X - 1 != -1 and Table[X - 1][Y] and (X - 1, Y) not in Visited: 
     Queue.append ((X - 1, Y, Dist + 1)) 
    if Y - 1 != -1 and Table[X][Y - 1] and (X, Y - 1) not in Visited: 
     Queue.append ((X, Y - 1, Dist + 1)) 

Queue.append ((startx, starty, 0)) 
while (len(Queue)): 
    CurrentX, CurrentY, Distance = Queue.popleft() 
    if ((CurrentX, CurrentY) in Visited): continue 
    Visited.add ((CurrentX, CurrentY)) 
    process (CurrentX, CurrentY, Distance) 

Answer 3

내가 간단한 홍수 채우기 유형의 알고리즘을 사용하십시오 : -

create array of integers equal in size to boolean array => map 
set all values in map to 0 
set value at (start x, end x) to 1 
found path = false 
step = 1 

while !found path 
    for each cell in map where value == step 
    for each valid adjacent cell 
     if cell == end position 
     map [cell] = step 
     found path = true 
     end search 
     end if 
     if map [adjacent cell] == 0 
     map [adjacent cell] = step + 1 
     end if 
    end for 
    end for 
end while 

number of steps between start cell and end cell inclusive == step 

당신은 향상시킬 수 있습니다 효율성을 아주 쉽게 스택과 대기열을 사용합니다. 가능한 경로가없는지도를 확인해야합니다.