1
벽을 통과 할 수있는 능력이 없으면 나는 이것이 표준 다이 슐라의 문제라고 생각했습니다. 그러나 벽을 통과하거나 우회하는 X 배를받은 경우 Dijkstra의 알고리즘을 적용하기 위해 어떻게 모델링 할 수 있습니까?제한된 수의 벽을 통과 할 수있는 미로의 최단 경로?
A
답변
6
미로를 그래프로 표시한다고 가정합니다. 그래프의 X + 1 복사본을 생성하고 벽 사이에 인접한 셀에 대해 레벨 i과 레벨 i + 1 사이의 방향성있는 가장자리를 만듭니다. 마지막으로 모든 출구를 병합합니다.
실용적인 관점에서 볼 때 그래프의 사본을 만들 필요는 없으며 순서쌍 (정점, 레벨) 만 추적하면됩니다.
그건 까다 롭습니다. 모든 정점에 대해 허용되는 바이 패스 횟수마다 최단 경로를 저장해야합니다. 그것은 Dijkstra 's의 탐욕스러운 본성과 충돌합니다. –
벽을 통해 이동하고 통로를 통해 이동하는 비용은 얼마입니까? 그들은 모든 세포에서 동일합니까? 그들은 우리가 벽을 통해 얼마나 많이 움직 였는지에 달려 있습니까? – Gassa
통행 및 벽 통과 비용 1 (단계), 모두 동일 – nkt