바둑
시간 제한2초메모리 제한512 MB
빈 칸을 검은 돌로 채워 흰 돌을 잡을 수 있고, 흰 돌은 인접한 빈 칸이 하나도 없을 때 제거된다. 마지막에 남는 빈 칸 수의 최댓값을 구한다.
문제
민호와 강호가 바둑을 두고 있다. 민호는 흑돌, 강호는 백돌을 잡았다.
지금 바둑판 위에는 서로 인접한 백돌이 없다. 강호는 이미 항복해서 돌을 더 놓지 못한다. 민호는 돌을 더 놓을 수 있으며, 바둑판의 빈 칸 개수를 최대로 만들려고 한다.
민호는 빈 칸에 흑돌을 올려놓을 수 있다. 올려놓은 뒤에는 죽은 백돌을 바둑판에서 모두 제거한다. 백돌이 죽었다는 것은 그 돌이 놓인 칸과 인접한 칸에 빈 칸이 하나도 없다는 뜻이다. 두 칸은 변을 맞대고 있을 때 인접하다.
바둑판의 상태가 주어졌을 때, 민호가 만들 수 있는 빈 칸 개수의 최댓값을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 바둑판의 가로와 세로 크기 N이 주어진다. (3 ≤ N ≤ 50)
둘째 줄부터 N개의 줄에 바둑판의 상태가 한 줄에 N개의 글자로 주어진다. 각 글자는 다음 셋 중 하나다.
- 'o': 백돌
- 'x': 흑돌
- '.': 빈 칸
서로 인접한 백돌은 없으며, 모든 백돌은 적어도 하나의 빈 칸과 인접해 있다.
출력
첫째 줄에 민호가 만들 수 있는 빈 칸 개수의 최댓값을 출력한다.
힌트
흑돌을 하나 놓을 때마다 빈 칸이 하나 줄고, 백돌을 하나 제거할 때마다 빈 칸이 하나 늘어난다. 백돌 하나를 잡으려면 그 돌과 인접한 빈 칸을 모두 흑돌로 채워야 한다. 서로 인접한 백돌은 없으므로, 백돌을 제거해서 생긴 빈 칸이 다른 백돌을 살리는 일은 없다. 민호가 돌을 하나도 놓지 않는 것도 가능하다.