시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
5 초 | 512 MB | 40 | 19 | 17 | 44.737% |
당신은 한 제약회사에서 근무하고 있다. 이 제약회사는 최근 박테리아 샘플을 보관하기 위해서 건물을 지었는데, 이 건물은 여러 층으로 이루어져 있으며 각 층에는 직각 다각형 모양의 방들이 있다. 회사는 이 건물의 모든 방에 박테리아 샘플을 보관하려고 계획했지만, 건물 설계상의 치명적 결함이 발견되어서 그럴 수 없게 되었다. 천장과 바닥 사이의 마감이 완벽하지 못해서 위아래로 인접한 방 양쪽에 박테리아 샘플이 있다면 둘이 서로 섞일 위험이 발견된 것이다. 이 문제 때문에 회사는 위아래 층으로 서로 인접한 방에는 동시에 박테리아를 보관하지 않기로 했고, 박테리아를 보관하지 않는 방에는 살균 설비를 설치해서 오염이 일어나지 않도록 조치하려고 한다. 당신의 임무는 조건을 만족하면서 이 건물에서 최대 몇 개의 방에 박테리아를 보관할 수 있는지 알아내는 것이다.
입력의 첫 줄에는 테스트 케이스의 숫자 T가 주어진다. 아래로는 T개의 테스트 케이스가 다음과 같이 주어진다.
N M K B1,1,1B1,2,1 … B1,M,1 B2,1,1B2,2,1 … B2,M,1 … BN,1,1BN,2,1 … BN,M,1 … BN,1,KBN,2,K … BN,M,K
여기서 N은 건물 한 층의 행 수, M은 건물 한 층의 열 수, K는 건물의 층 수를 나타낸다. Bi,j,k는 ‘.’ 인 경우 해당 칸이 비어있음을, ‘#’인 경우 해당 칸이 벽임을 나타내며, 한 층에서 가로/세로로 인접한 빈 칸들은 하나의 방에 속한다. 예를 들어 다음과 같은 구조의 층에는 A, B, C 세 개의 방이 있다. 하나의 방이 두 개 이상의 층에 걸쳐있는 경우는 없다.
#..# // #AA# ###. // ###B ..#. // CC#B #..# // #CC#
각 테스트 케이스에 대한 출력은 "Case #x: y" 형태로 이루어져야 한다. x는 1부터 시작되는 케이스 번호이고, y는 해당 케이스에 대해서 박테리아를 보관할 방의 최대 숫자이다.
3 3 3 3 ... ### ... .## .#. .#. .## ### .## 4 4 2 .#.. #.#. .#.. #.#. .#.# ..#. .#.# ..#. 1 5 3 ...## .#.#. ##...
Case #1: 4 Case #2: 8 Case #3: 3
Contest > Google > Google's Coding Competitions > Google Code Jam Korea 2012 > Code Jam Korea 2012 본선 2차 라운드 C2번