IOI 1994 day1 2- 방면적 넓히기(The Castle) > 문제은행 : 정보올림피아드&알고리즘




1364 : 방면적 넓히기(The Castle)

제한시간
1000 ms   
메모리제한
128 MB   
해결횟수
55 회   
시도횟수
179 회   

문제

어느날 동훈이가 로또 1등에 당첨 되었다. 갑작스레 얻은 돈으로 무엇을 할까 고민하다. 

유명한 아파트인 타이어펠리스에 입주를 하고자 하였다.

 

이사를 하기 전에 방을 살펴보던 도중 생각보다 방이 좁다고 느낀 동훈이는 자신이 거주하게 될 방을 최대한 크게 하기 위해서 벽을 허물고자 하였다. 

하지만 많은 벽을 허물 경우 건물 자체에 무리가 생기기 때문에 타이어펠리스의 관리자는 벽을 딱 한 개만 허물 수 있도록 허가 하였다.

 

아파트가 제법 넓기 때문에 다음과 같은 설계 도면을 받아서 허물 벽을 결정하려고 한다. 

아파트의 도면은 다음과 같이 주어지며 한 칸의 넓이는 1이며 ‘#’는 벽을 의미하며 ‘|’는 이미 뚫려 있는 곳을 의미한다. 

방 하나는 벽으로 완전히 둘러싸인 공간을 말한다.

 


 

위의 경우 기존의 방의 개수는 5개 이며, 가장 큰 방의 면적은 9이다. 

여기서 (4,1)의 동쪽의 벽을 허물 경우 가장 큰 면적이 16으로 증가한다.

위와 같은 설계 도면에 대한 데이터가 주어졌을 때 처음의 방의 개수, 가장 큰 방의 면적, 

그리고 벽 하나를 허물었을 경우의 면적과, 어느곳을 허물어야 하는지를 알아보는 프로그램을 작성하라.

 


입력형식

입력은 첫 번째 줄에 아파트의 가로 길이 M, 세로 길이 N이 주어진다. M과 N은 1이상 50이하의 값이다. 두 번째 줄부터 N개의 줄에는 M개의 숫자가 주어지는데, 이는 설계도면의 데이터 이며 (1,1)부터 (N, M)까지의 칸에 대한 정보가 순서대로 주어진다. 각각의 칸에 대한 정보는 벽이 있는가에 대한 정보인데, 한 칸에 대해 다음과 같은 숫자의 합으로 표현이 된다.

1 : 서쪽(왼쪽)에 벽이 있을 경우 2 : 북쪽(위쪽)에 벽이 있을 경우 4 : 동쪽(오른쪽)에 벽이 있을 경우 8 : 남쪽(아래쪽)에 벽이 있을 경우

가령 (1,1)의 경우 서, 북, 남쪽에 벽이 있으므로 1+2+8 = 11 로 표현 된다.


출력형식

입력된 설계도면에 대해 다음 값들을 출력한다. 첫 번째 줄 : 기존 방의 개수 두 번째 줄 : 가장 큰 방의 면적 세 번째 줄 : 벽을 하나 허물었을 경우 가장 큰 방의 면적 네 번째 줄 : 가장 큰 방을 얻기 위해서 허물 방의 위치와 그 방에서 본 벽의 방향 네 번째 줄의 경우 우선 세로위치, 가로위치를 빈칸을 두고 출력하고 빈칸 뒤에 허물벽의 방향에 대한 영어 대문자를 출력한다. (동, 서, 남, 북의 약자는 각각 'E', 'W', 'S', 'N' 와 같다.)

허물었을 경우 가장 큰 방을 얻을 수 있는 벽이 여러 개 있을 경우 그 벽을 허물수 있는 가장 서쪽의 방을 우선하여 선택한다. 가장 서쪽에 있는 방이 여러 개인 경우 가장 남쪽에 있는 방을 우선하여 선택한다.

선택된 방에서 허물 수 있는 벽이 여러 개인 경우 북쪽을 우선으로 동쪽을 차선으로 하여 선택한다.

입력 예

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


경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP