격자 탈출 timer 20s memory 1024MB

당신은 R행 C열의 직사각 격자 방(단위 칸)으로 이루어진 새로운 "탈출" 어드벤처를 설계하고 있다. 각 방에는 격자의 네 직교 방향(북, 남, 동, 서)에 대응하는 네 개의 문이 있다. 격자 경계에 있는 문은 바깥으로 이어지고, 그 외의 문은 다른 방으로 이어진다.

이 어드벤처는 정확히 R × C명의 플레이어가 플레이하며, 각 플레이어는 서로 다른 R × C개의 방 중 하나에서 시작한다. 모두 자리에 들어가 게임이 시작되면, 모든 문이 닫히고 기계적인 장치가 작동한다: 각 방에서 네 개의 문 중 하나는 그 방 안쪽에서 열 수 있고, 나머지 세 개의 문은 열 수 없다. 이는 어드벤처 내내 일관되며, 어떤 방에서든 열 수 있는 문은 항상 같은 문이다. 두 방을 연결하는 문이 한쪽에서는 열리지만 다른 쪽에서는 열리지 않을 수도 있다는 점에 유의하라.

각 플레이어는 다른 모든 플레이어와 독립적으로 움직인다. 플레이어는 자신이 직접 연 문으로만 통과할 수 있으며, 문을 통과한 뒤에는 문을 닫아야 한다. 각 플레이어는 바깥으로 이어지는 문을 통과해 탈출하거나, 탈출하지 못한 채로 R × C번 이동할 때까지 계속 문을 통과한다. (후자의 경우 그 플레이어는 실패한 것으로 간주되며 탈출하지 못한다.)

당신은 각 방에서 어떤 문이 열리도록 할지 정해서, 정확히 K명의 플레이어만 탈출할 수 있게 하고 싶다. 그렇게 하는 방법을 찾거나, 불가능하다면 IMPOSSIBLE을 출력하라.