Informatica Online Judge

  The Castle (성, IOI-94) [0270 / 010E]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 30   Total Tried : 35


The Champion of this Problem (C++) : N/A
My Best Submission (C++) : N/A

[]

Background

농부 존은 자신의 생일날 일생에서 가장 운이 좋은 일이 일어났다.

그가 산 복권이 1등으로 당첨된 것이다. 그는 어마어마한 상금으로 유럽 근교에 있는 매우 근사한 성을 샀다.

농부 존은 이 성을 자신의 젖소들에게 자랑하고 싶어졌다. 그는 이 성에 얼마나 많은 방들이 있는지, 그리고 가장 큰 방의 크기는 얼마인지 등의 내용이 자랑하고자 하는 내용이었다.

농부존이 가진 성은 정확하게 몇 개의 방을 가지는 지 그리고 가장 큰 방의 크기는 얼마인지,

마지막으로 벽 하나를 뚫을 수 있다고 할 때, 제거되는 벽에 의해서 새로 생기는 새로운 방이 가장 큰 방이된다고 할 때, 이 방의 크기는 얼마인지를 알 수 있도록 도와주자.

성의 평면도는 아래와 같다.



#-벽, |,--- 는 통과 가능한 길,
->는 제거하고자 하는 벽(제거 했을 때 가장 큰 방을 만들 수 있음)

성의 평면도를 보면 성은 M(폭)*N(높이)공간으로 구성되어 있으며, 벽은 성 내부의 벽만 뚫을 수 있고, 외곽의 벽은 절대로 뚫을 수 없다.

위 예시로 주어진 성의 경우 7*4의 크기의 성이고, 방은 총 5개로 구성되며 각 방의 크기는 9, 7, 3, 1, 8이다.

-> 마크가 있는 벽을 제거할 경우 가장 큰 방의 크기는 16이 된다.

Input

첫 번째 줄에는 두 개의 정수 M과 N이 공백으로 구분되어 입력된다. (M,N은 50이하의 자연수이다.)

두 번째 줄에는 1, 2, 4, 8의 합으로 표현된 정수가 한 줄에 M개씩 N줄이 공백으로 구분되어 입력된다.

여기서 각 숫자의 의미는 다음과 같다.

1 : 벽이 서쪽에 있다.
2 : 벽이 북쪽에 있다.
4 : 벽이 동쪽에 있다.
8 : 벽이 남쪽에 있다.

만약 11이었다면 현재 공간에서 벽이 서, 북, 남쪽에 있다는 의미이다.

Output

첫 번째 줄에는 이 성이 가지는 방의 개수를
두 번째 줄에는 이 성에서 가장 큰 방의 크기를
세 번째 줄에는 하나의 벽을 제거함으로써 생기는 가장 큰 방의 크기를
마지막 줄에는 제거할 벽의 좌표 그 방에서 제거해야할 벽의 방향(N, E, S, W)을 출력한다.

(단, 제거해야 조건을 만족하는 벽이 여러 개 있을 경우에는 가장 서쪽에 있는 공간을 선택한다. 그래도 여전히 같다면 가장 남쪽에 있는 공간을 선택한다. 그래도 여전히 같다면 N을 E보다 우선한다.)

IO Example

입력
7 4
11 6 11 6 3 10 6
7 9 6 13 5 15 5
1 10 12 7 13 7 5
13 11 10 8 10 12 13

출력
5
9
16
4 1 E


IOI(International Olympiad in Informatics) - 1994

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]