문제
R행 C열의 격자 모양의 지역에 몇 명의 사람이 서 있다. 한 격자에는 최대 한 명의 사람이 있다.
각 사람들은 자신과 인접한 사람과 정확히 한 번씩 악수하는데, 인접한 사람은 아래 그림과 같이 주위 8방향에 있는 사람을 말한다.
민혁이는 이 지역의 빈 격자 중 한 곳에 들어가서 이 지역에서 일어난 악수의 총 횟수가 최대가 되게 하려고 한다.
민혁이가 들어간 후 이 지역에서 일어난 악수의 총 횟수를 구하여라. 만약 빈 격자가 없다면 민혁이는 아무 행동도 하지 않는다.
입력
첫 번째 줄에는 격자의 크기 R, C가 주어진다. (1 ≤ R, C ≤ 50)
두 번째 줄부터 R개의 줄에는 이 지역의 현재 상태가 주어진다. 'O'는 사람이 있는 곳을, '.'는 사람이 없는 곳을 나타낸다.
출력
민혁이가 들어간 후 이 지역에서 일어난 악수의 총 횟수를 출력한다.
예제1
입력
23
..o
o..
출력
2
예제2
입력
22
oo
oo
출력
6
힌트
출처
COCI 2013/2014 - Contest 2