달리는 두더지 timer 1s memory 1024MB

두더지가 정올이네 마당에 W \times L크기의 직사각형 격자 모양의 터널로 구멍을 뚫었다!

피해에 격분한 정올이는 두더지를 잡기 위해 N 마리의 테리어를 마당에 풀어 놓았다.

테리어는 매우 민감한 청각을 가지고 있어 두더지에 충분히 가까이 다가가면 매우 빠르게 땅을 파서 설치류를 잡을 수 있다.

안타깝게도 두더지는 테리어의 발자국 소리에 매우 민감하여 적극적으로 테리어를 피하려고 한다.

정올이는 테리어가 풀려났을 때 두더지가 어디에 있었는지 전혀 모르지만 정올이는 한동안 테리어들이 마당을 돌아다니는 것을 지켜봤다.

정올이가 관찰한 내용을 바탕으로 두더지가 어디에 있을지 추론하는 프로그램을 작성하시오.

처음 정올이가 테리어를 마당에 각 위치에 풀어놨을 때는 두더지는 테리어의 아래나 근처에 있지 않았다.

이후의 각 시간이 흐름에따라 테리어는 동일한 위치에 남아 있을 수도 있고 수평 또는 수직으로 한 칸 이동할 수도 있다. (시간대별 테리어의 위치는 모두 정올이가 기록을 해두었다)

그러면 두더지도 똑같이 동일한 위치에 남아 있을 수도 있고 수평 또는 수직으로 한 칸 이동했을 수도 있다.

테리어나 두더지가 이러한 움직임을 하기 전후에 테리어가 두더지 바로 위에 있거나 두더지에 인접한 위치(수평 또는 수직)에 있었다면 두더지는 잡혔을 것이다.

프로그램은 T 시간이 지났을 때의 테리어에게 잡히지 않고남은 두더지의 가능한 위치 목록을 출력해야 한다.