COCI 2013/2014 - Contest 2- 악수(MISA) > 문제은행 : 정보올림피아드&알고리즘




2669 : 악수(MISA)

제한시간
1000 ms   
메모리제한
32 MB   
해결횟수
109 회   
시도횟수
311 회   

문제

R행 C열의 격자 모양의 지역에 몇 명의 사람이 서 있다. 한 격자에는 최대 한 명의 사람이 있다.

 


각 사람들은 자신과 인접한 사람과 정확히 한 번씩 악수하는데, 인접한 사람은 아래 그림과 같이 주위 8방향에 있는 사람을 말한다.



민혁이는 이 지역의 빈 격자 중 한 곳에 들어가서 이 지역에서 일어난 악수의 총 횟수가 최대가 되게 하려고 한다.

 

민혁이가 들어간 후 이 지역에서 일어난 악수의 총 횟수를 구하여라. 만약 빈 격자가 없다면 민혁이는 아무 행동도 하지 않는다.

 


입력형식

첫 번째 줄에는 격자의 크기 R, C가 주어진다. (1 ≤ R, C ≤ 50) 두 번째 줄부터 R개의 줄에는 이 지역의 현재 상태가 주어진다. 'O'는 사람이 있는 곳을, '.'는 사람이 없는 곳을 나타낸다.

출력형식

민혁이가 들어간 후 이 지역에서 일어난 악수의 총 횟수를 출력한다.

입력 예

2 3
..o
o..

출력 예

2

입력 예

2 2
oo
oo

출력 예

6

Hint!

민혁이가 1행 2열 또는 2행 2열에 들어가면 민혁이가 기존에 있던 두 사람과 악수하게 되어 총 2번의 악수가 일어난다.



경기도 안양시 동안구 평촌대로 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