레이팅 미적용설명
연구실 강의실은 \(R\)행 \(C\)열의 좌석 격자로 이루어져 있다. 사용할 수 있는 좌석은 ., 고장 난 좌석은 #으로 표시된다.
연구원들이 집중할 수 있도록, 상하좌우로 인접한 두 좌석에는 동시에 사람을 앉힐 수 없다. 대각선으로 인접한 좌석은 함께 사용할 수 있다.
조건을 만족하면서 앉힐 수 있는 연구원의 최대 인원수를 구하여라.
제약
- \(1 \le R \le 100\)
- \(1 \le C \le 12\)
- 각 칸은
.또는#이다.
입력 형식
첫째 줄에 행의 수 \(R\)과 열의 수 \(C\)가 주어진다.
다음 \(R\)개의 줄에 길이 \(C\)의 좌석 문자열이 주어진다.
출력 형식
앉힐 수 있는 연구원의 최대 인원수를 출력한다.
서브태스크
| 서브태스크 | 점수 | 설명 |
|---|---|---|
Subtask 1 | 20점 | \(1 \le R,C \le 4\) |
Subtask 2 | 80점 | 추가 제한이 없다. |
예제 1
입력
3 3
...
.#.
...
출력
4
설명
네 모서리 좌석을 사용하면 연구원 4명을 앉힐 수 있다.
예제 2
입력
1 4
.#.#
출력
2
설명
사용 가능한 두 좌석은 서로 인접하지 않아 모두 사용할 수 있다.
문제 정보
rip 작성
출처 RiseOJ Original
태그