함정 설치
문제 정보
-
- 문제 ID
- 시간 제한
- 메모리 제한
- 제출 횟수
- 정답 횟수 (비율)
-
- 출처
- 분류
문제
막강한 권력을 자랑하는 악당들의 모임인 지옥화염 클럽은 정의의 사도 Z남자들의 침입으로 망가진 기지를 버리고 새 지하 기지에 입주하기로 하였습니다. 이 지하 기지는 화려한 인테리어와 회의실, 홈시어터, 볼링장, 구내 식당 등의 시설을 완비했지만, 빠진 것이 하나 있습니다. 바로 함정이지요. 시대와 장소를 막론하고 악당들의 지하 기지에는 다양한 함정이 설치되어 있어야 하기 때문입니다.
| (a) | (b) |
|---|---|
 |
 |
지옥화염 클럽의 지하 기지는 그림 (a)와 같은 직사각형 형태로, 기지 내부는 H*W 개의 구간으로 나뉘어져 있습니다. 각 칸은 복도나 방처럼 뚫려 있거나(흰 칸) 벽이나 기둥으로 막혀 있습니다(검은 칸). 지옥화염 클럽은 클럽 회원들의 통행을 불편하게 하지 않는 선에서 가능한 많은 함정을 설치하려 합니다. 클럽 회원들은 모두 기억력이 좋아 함정의 위치를 쉽게 외울 수 있으며, 한 칸 정도는 가볍게 뛰어넘을 수 있는 신체 능력을 가졌기 때문에 왠만해서는 함정을 피해 다닐 수 있습니다. 그러나 서로 변을 맞댄 두 칸에 모두 함정을 설치할 경우 통행이 불편해지므로 이런 일이 없도록 하고 싶습니다. 그림 (b)는 (a)의 지도에서 함정을 설치할 수 있는 방법을 보여줍니다.
지하 기지의 지도가 주어질 때 어떻게 배치해야 가장 많은 함정을 설치할 수 있을지 계산하는 프로그램을 작성하세요.
입력
입력의 첫 줄에는 테스트 케이스의 수 C (C <= 50) 가 주어집니다. 각 테스트 케이스의 첫 줄에는 지하 기지의 크기 H, W (1 <= H,W <= 20) 이 주어집니다. 그 후 H 줄에 각 W 글자로 지하 기지의 지도가 주어집니다. 이 문자열에서 #는 벽으로 막힌 칸, .는 빈 칸을 나타냅니다.
출력
각 테스트 케이스마다 우선 설치할 수 있는 함정의 최대 수를 출력하고, 그 후 함정의 위치를 포함한 지하 기지의 지도를 다시 출력합니다. 함정을 설치할 빈 칸은 . 대신 ^ 로 표시하며, 함정을 설치하는 방법이 여러 개 있다면 그 중 아무 것이나 선택해도 됩니다.
예제 입력
2 5 3 ... #.# #.# #.# ... 6 10 ###.###.## .##.....#. ..#.###... ..###..##. .####..#.# ..........
예제 출력
6 ^.^ #^# #.# #^# ^.^ 19 ###^###^## .##.^.^.#^ ^.#^###.^. .^###^.##^ ^####.^#^# .^.^.^.^.^
노트
