평면도

면접 대비

시간 제한1초메모리 제한128 MB

요약
벽과 바닥 칸으로 이루어진 격자에서 연결된 방의 크기를 구해 큰 방부터 순서대로 바닥재를 깔고, 바닥재를 받은 방의 수와 남은 양을 출력한다.
난이도

보통10점 중 4점

유형
DFS, 정렬, 구현, 배열
정답자
아직 제출이 없습니다

문제

집의 평면도가 격자 위에 주어진다. 문자 I는 벽을, 문자 .은 방의 바닥 공간을 나타내며, 각 문자는 11 제곱미터를 차지한다. 문(출입구)은 표시되지 않는다.

하나의 방은 가로 또는 세로로 인접하여 서로 연결된 . 칸들의 최대 묶음이다. 어떤 방도 6464 제곱미터를 넘지 않는다.

당신에게는 일정한 제곱미터의 원목 마루가 주어진다. 가장 큰 방부터 시작하여 그다음으로 큰 방으로 차례대로 마루를 시공한다. 한 방을 시공하려면 그 방의 넓이만큼의 마루가 필요하며, 어떤 방도 건너뛸 수 없다. 다음 방을 시공할 만큼의 마루가 남아 있지 않으면 즉시 멈춘다.

마루가 시공되는 방의 개수와 남는 마루의 넓이(제곱미터)를 출력하라.

입력

  • 첫째 줄: 보유한 마루의 넓이(제곱미터)를 나타내는 정수.
  • 둘째 줄: 격자의 행 수를 나타내는 정수 rr (1≤r≤251 \le r \le 25).
  • 셋째 줄: 격자의 열 수를 나타내는 정수 cc (1≤c≤251 \le c \le 25).
  • 이후 rr개의 줄: 각 줄에 격자 데이터를 이루는 cc개의 문자(I 또는 .).

출력

정확히 다음 형식의 한 줄을 출력한다.

K rooms, M square metre(s) left over

여기서 KK는 마루가 시공된 방의 개수, MM은 남은 마루의 넓이(제곱미터)이다.

예제2

  1. 예제 1

    입력
    105
14
16
IIIIIIIIIIIIIIII
I......I.......I
I......III.....I
I........I.....I
I........IIIIIII
IIIIIIIIII.....I
I.I......I.....I
III..III.I.....I
I....I.IIIII...I
I....I.....III.I
I....I.......I.I
I....I.....III.I
I....I.....I...I
IIIIIIIIIIIIIIII
    예상 출력
    4 rooms, 1 square metre(s) left over

  2. 예제 2

    입력
    13
2
3
.I.
.I.
    예상 출력
    2 rooms, 9 square metre(s) left over