c 푸시박스 문제

먼저 아이디어부터 이야기해보자.

k부터 시작하세요. P가 k에 들어가도록 하려면 k에 인접한 w에서 밀어야 합니다. 따라서 지점을 확장하십시오. p와 m은 마지막 단계에서 결정됩니다.

다음 단계에서는 p와 m의 위치가 결정됩니다. 그런 다음 m이 이전 단계의 m 위치에 연결될 수 있는지, 즉 도달할 수 있는지 계산합니다.

P가 원래 정해진 장소로 돌아올 때까지. m은 원래 위치로 돌아갈 수 있습니다. 해결될 수 있다는 것이 증명되었습니다. 재귀 깊이를 계산하는 것은 p 이동 단계 수입니다.

특정 단계를 해결할 수 없으면 직접 재귀에서 벗어나 해결책이 없음을 증명하세요.

문제는 이것이 최적의 솔루션이라는 증거가 여기에 없다는 것입니다. 하나의 분기를 통해서만 솔루션을 찾을 수 있는 경우 모든 분기가 완료될 때까지의 단계 수를 최적 솔루션으로 기록합니다.