역 추적 재귀를 사용하여 자체 회피 보행

Question

주어진 : 그리드 m × n
하나 이상의 교차로가 있고 역 추적과 재귀를 사용하여 오른쪽 상단에서 끝나는 모든 경로를 열거해야합니다! 어떤 제안.?
Self-Avoiding Walk

Answer 1

비 재귀 방법은 이전의 위치와 그 위치에서 의사 결정을 필요로하는 정보의 스택을 유지하는 것입니다. 결정이 내려 질 때마다 저장해야하는 정보를 스택 맨 위에 밀어 넣으십시오.

그런 다음 검색에서 문제가 발견되면 스택을 팝하고 가장 최근의 결정 포인트로 돌아가서 다른 결정을 내립니다. 결국 당신은 성공하거나 모든 가능한 경로를 불가능한 것으로 제거합니다.

재귀 적 솔루션의 경우 정보를 스택에 푸시하는 대신 재귀 호출에서 결정한 후에 새 위치를 전달합니다. 재귀 호출이 실패를 반환하면 현재 위치에서 다음 가능한 결정을 시도합니다. 현재 위치에서 선택 사항을 모두 사용하지 못하면 위의 레벨로 실패를 리턴하십시오. 재귀 호출이 성공을 반환하는 경우에만이 수준에서 성공을 반환합니다.

마지막으로 성공은 전체 호출 체인에서 반환되거나 가능한 모든 경로는 제거됩니다.

숙제이기 때문에 한 수준에서 다른 수준으로 전달해야하는 정보와 최종 성공 경로를 응용 프로그램에 반환하는 방법을 직접 결정해야합니다.

필요한 모든 새로운 아이디어는 위의 단락에 나와 있습니다. 구현은 당신에게 달려 있습니다.

- 제시