임무 : 주어진 임의의 크기의 미로에서 빨리 출구를 찾아 그 경로만을 화면에 출력한다.
조건
- 미로의 모양은 사각형(정사각형이 아닐 수도 있다) 이나 그 크기는 미리 알지 못한다.
- 미로의 크기가 [0…n][0…m] (즉행의 수가 n 이고 열의 수가 m)일 때 입구는 항상 [0,1]에 위치한다.
- 갈수 있는 길은 0으로 표시되고 벽은 1로 표시된다.
- 미로를 지나는 쥐는 최초에 n x m X 2의 에너지를 지닌다. 한칸 움질일 때 마다 에너지 1씩 감소. 에너지가 1.0보다 작으면 더 이상 못 움직임.
- 미로의 상하, 좌우로만 움직일 수 있고 사선 형태로는 움직일 수 없다.
- 미로의 출구가 오직 하나 존재하며 위치는 정해지지 않았다. (외부 벽은 입구와 출구를 제외하고 모두 1)
- 쥐는 마나(mana)를 가지고 있으며 초기에는 0이다. 쥐가 1칸 이동할 때 마다 0.1의 마나가 쌓이며 마나 1을 소비하여 3x3 을 scan 할 수 있으며 마나 3을 소비하면 벽 하나를 뚤을 수 있다 (단 외벽은 파괴할 수 없음).
쥐는 이동할 때 마다 갈 수 있는 방향을 stack에 넣는다. 우선순위는[ 오른쪽, 아래, 위, 왼쪽 ]이다.
스택은 후입선출 이므로, 우선순위와 반대로 스택에 넣어야 한다.
출구의 위치를 8방향으로 생각하고, 출구의 위치에 따라 쥐의 이동방향 우선순위를 바꾼다.
쥐의 현재 위치에서 3면이 벽으로 막혀있다면, 되돌아 오면서 길을 막는다.
입구가 왼쪽 위 구석에 있으므로, 최대한 멀리서 탐색하도록 오른쪽 밑에서부터 스캔을 뿌리도록 한다. 출구는 경계 벽에 있으므로 스캔을 경계를 따라 시계방향으로 사용한다.
쥐의 이동 우선순위가 오른쪽 아래이므로 잘 확인이 되지 않을 왼쪽 아래 부분을 스캔으로 확인한다.
출구를 찾았다면 가상의 스캔 쥐(Scan Rat)을 만들어서 출구로 부터 현재 쥐가 있는 길을 찾도록 한다. 스캔 쥐는 스캔을 사용할 위치를 의미한다.
스캔으로 확인한 길은 모두 출구로 이어지는 확정 길로 만든다. 스캔 쥐는 확정길만 따라서 움직이고, 만약 스캔 쥐가 미개척지(아직 모르는 길)를 만나게 되면 스캔의 효율성을 위해 바라보는 방향의 2칸 앞에다가 스캔 장소를 설정하고, 스캔 쥐의 이동을 멈춘다.
쥐가 출구로 가는 확정길을 찾은 경우, 더 이상 스캔을 사용하지 않는다.
쥐가 출구로 가는 확정 길을 찾았을 경우, 벙커버스터를 사용한다. 벙커버스터는 쥐의 현재 위치에서 벽 뒤로 출구로 가는 확정 길이 있을 때 사용한다. 쥐는 벽을 부숴 생긴 길을 따라간다. 만약 갈림길이 있다면 출구로 가는 방향이 아니면 길을 막는다.
