왕의 미로

Question

나는 프로그래밍 경쟁을 실천하고 있으며, 나는 과거에 대답 할 수 없었던 어려운 문제들을 다룰 것입니다. 그들 중 하나는 King 's Maze였습니다. 본질적으로 "토큰"을 나타내는 NXN 숫자 배열 -50<x<50이 제공됩니다. 당신은 위치 1,1 (배열 색인에서 0,0이라고 가정)에서 시작하여 N, N으로 끝내야합니다. 방문한 셀에서 토큰을 선택해야하며 토큰이없는 셀 (0으로 표시)으로 이동할 수 없습니다. 0으로 둘러싸인다면 잃을 수 있습니다. 미로에 대한 해결책이 없다면 "해결책 없음"을 출력합니다. 그렇지 않으면, 당신은 당신이 데리러 토큰을 추가에서 얻을 수있는 가능한 가장 높은 숫자를 출력합니다.

이 문제를 해결하는 방법을 모르겠습니다. 난 당신이 그것을 해결하기 위해 미로 알고리즘을 쓸 수 있다고 생각했지만 시간이 걸리고, 프로그래밍 경연 대회에서는 여러 문제를 풀기 위해 2 시간 밖에 주어지지 않습니다. 내가 놓친 어떤 종류의 패턴이있는 것 같아. 아무도 내가이 문제에 어떻게 접근해야하는지 안다?

또한이 문제는 고등학생에게 의미가 있음을 알 수 있습니다.

Answer 1

이러한 유형의 문제는 일반적으로 dynamic programming 또는 memoization을 사용하여 해결됩니다.

기본적으로 재귀 적 솔루션을 공식화하고 이전에 계산 된 결과를 기억하고 재사용하면서 아래쪽으로 풀면됩니다.

Answer 2

생각 "그래프"알고리즘 : The Algorithm Design Manual

Answer 3

간단한 접근법 (즉 단순한 코드) 모든 가능한 경로들을 시도이다 - 각 먼저 시도; 각 첫 번째 단계마다 두 번째 단계를 시도하십시오. 각각의 제 1 단계/제 2 단계 조합에 대해 각각의 제 3 단계를 시도; 등등. 그러나 미로가 얼마나 큰가에 따라 달리기에는 너무 오래 걸릴 수도 있습니다 (그렇지 않을 수도 있습니다).

다음 단계는이를 더 빨리 수행 할 수있는 방법에 대해 생각하는 것입니다. 첫 번째 단계는 대개 마무리로 이어지지 못하는 동작을 제거하거나 이미 가지고있는 것보다 높은 포인트로 마무리 할 수없는 것입니다. 이것은 경쟁을위한 연습이기 때문에 우리는 당신이 직접이 일을 맡길 것입니다.