한 지점에서 한 지점까지 유효 도로 가져 오기 (매트릭스의 BFS)

Question

저는 0과 X가있는 행렬을 가지고 있습니다 (0은 걸을 수 있고 X는 벽을 의미 함). 시작 지점과 끝 지점이 있습니다. BFS를 사용하여 시작과 끝 사이의 최단 경로 (길이)를 찾습니다. (작동) 하지만 이제는 효과적인 도로를 찾아야하고 어떻게해야할지 모르겠다. (나는이 알고리즘 재귀를 사용할 수 있다고 생각했다.)

Example: 

5 5 
SXXXF 
0XX00 
0XX0X 
0000X 
XXXXX 

길이가 8 및도이며, (1, 1) -> (2, 1) -> (3, 1) -> (4, 2) -> (4, 3) -> (3, 4) -> (2,4) -> (1, 5)이다. 방향이 8 개 있습니다.

그래서 BFS를 사용하여 길이 (8)를 얻었지만 도로를 얻는 방법을 모르겠습니다. 몇 가지 아이디어 또는 의사 코드? 감사합니다.

Answer 1

사실 매우 간단합니다. 각 노드의 "선행 작업자"를 저장하십시오. 원래지도에 삽입 된 또 다른 행렬이거나 Map입니다. 양방향이라면 나무 구조조차도 작동 할 것입니다.

코드가 없으면 가능한 해결책을 제시 할 수 없지만 결국에는 node -> node from which it was visited 만 있으면됩니다. 예 : 예에서는 (1, 1)에서 (2, 1)으로 이동하므로 매핑은 (2, 1)->(1, 1)이됩니다. 이것은 BFS 루틴 내에서 쉽게 구현 될 수 있습니다.

매핑을 완료하면서 알고리즘 실행을 마칩니다. 그 다음에는 마침 노드의 선행 작업을 시작한 다음 마침 노드의 선행 작업을 시작한 다음 시작 지점으로 돌아갈 때까지 계속 작업을 시작합니다.