E D R , A S I H C RSS

Robbery


인기도:B(A,B,C), 성공률:보통(낮음,보통,높음), 레벨:3(1~4)

About Robbery

로보스탑 형사는 화가 머리 끝까지 나 있다. 지난 밤에 은행이 털렸는데, 은행강도를 잡지 못했기 때문이다. 사고가 난 직후, 강도가 도망갈 수 없도록 도시 밖으로 나가는 도로를 차단했다. 그리고 도시에 있는 모든 사람들에게 강도를 찾아달라는 요청을 했다. 하지만 그는 강도를 못 봤다는 말밖에 들을 수 없었다.

로보스탑은 강도가 정확하게 어떤 식으로 탈출했는지 반드시 알아내기로 결심했다. 로보스탑 형사가 당신에게 그가 가진 모든 정보를 분석해서 강도가 언제 어디에 있었는지 알아낼 수 있는 프로그램을 만들어달라고 요청했다.

그 범죄가 일어난 도시는 직사각형 모양으로 생겼다. 도시 밖으로 나가는 모든 도로는 시간 t 동안 봉쇄되어 있었고, 그 동안 "강도가 시간 t<sub>i</sub>에 직사각형 R<sub>i</sub>에 없다"는 식의 보고가 올라왔다. 그 강도가 각 시각 단계마다 최대 한 칸만 이동할 수 있다고 가정하고, 각 시각 단계에서의 강도의 정확한 위치를 찾아내라.

Input

한 입력 파일에 여러 테스트 케이스가 있을 수 있다. 각 테스트 케이스의 첫째 줄에는 세 개의 정수 W, H, t(1 ≤ W, H, t ≤ 100)가 들어있으며, W는 도시의 너비, H는 도시의 높이고, t는 도시가 봉쇄된 시간이다.

그 다음 줄에는 n(0 ≤ n ≤ 100)이라는 정수 한 개가 입력되는데, n은 형사가 받은 메시지의 개수다. 그 밑으로는 n줄에 걸쳐서 각 줄마다 다섯 개씩의 정수 t<sub>i</sub>,L<sub>i</sub>,T<sub>i</sub>,R<sub>i</sub>,B<sub>i</sub>가 입력된다. t<sub>i</sub>(1 ≤ t<sub>i</sub> ≤ t)는 메시지를 받은 시각이며, L<sub>i</sub>,T<sub>i</sub>,R<sub>i</sub>,B<sub>i</sub>는 각각 그 보고가 올라온 직사각형 영역의 왼쪽, 위쪽, 오른쪽, 아래쪽이다. (1,1)은 왼쪽 맨 위 영역이며, (W, H)는 오른쪽 맨 아래 영역이다. 그 메시지는 해당 시각 t<sub>i</sub>에 그 직사각형 안에 강도가 없었음을 의미한다.
W = H = t = 0 인 테스트 케이스가 입력되면 입력이 종료된다. 이 케이스는 처리하지 않는다.

Output

각 테스트 케이스에 대해 "Robbery #k:"라고 출력한다. 여기에서 k는 강도 사건 번호를 의미한다. 결과는 세 가지 경우로 나눌 수 있다.
강도가 도시 안에 있을 수 없는 경우에는 "The robber has escaped."라고 출력한다.
다른 경우에는 모두 강도가 여전히 도시 안에 있는 것으로 가정한다. 정확한 위치를 유추할 수 있는 경우에는 각 시간 단계에 대해 "Time step http://online-judge.uva.es/p/v7/707img5.gif: The robber has been at x,y."라고 출력한다. x와 y는 각각 시각이 http://online-judge.uva.es/p/v7/707img5.gif일 때 강도가 있는 위치의 열과 행을 나타낸다. 각 줄은 시각 http://online-judge.uva.es/p/v7/707img5.gif 순서대로 정렬해서 출력한다.
아무 결과도 유추할 수 없으면 형사가 화를 내지 않기를 기대하면서 "Nothing known."이라고 출력해야 한다.
각 테스트 케이스 사이에는 빈 줄을 출력한다.

Sample Input

{{| 4 4 5
4
1 1 1 4 3
1 1 1 3 4
4 1 1 3 4
4 4 2 4 4
10 10 3
1
2 1 1 10 10
0 0 0 |}}

Sample Output

{{| Robbery #1:
Time step 1: The robber has been at 4,4.
Time step 2: The robber has been at 4,3.
Time step 3: The robber has been at 4,2.
Time step 4: The robber has been at 4,1.

Robbery #2:
The robber has escaped. |}}

풀이

작성자 사용언어 개발시간 코드
조현태 C++ ? Robbery/조현태
Valid XHTML 1.0! Valid CSS! powered by MoniWiki
last modified 2011-05-22 07:17:29
Processing time 0.0893 sec