cho.sh옷장 방 (작은 입력)
기둥과 입구가 표시된 격자에 2칸짜리 옷장을 문 앞 칸이 비고 입구에서 도달 가능하도록 가장 많이 배치합니다.
보통6백트래킹완전 탐색BFS아직 제출이 없습니다시간 제한5초메모리 제한512 MB문제
의류 회사의 파스칼 사장은 재고로 남은 옷을 보관하려고 가로 W, 세로 H 크기의 창고를 빌렸다. 사장은 이 창고에 옷장을 최대한 많이 놓으려고 한다.
창고 바닥에는 가로 1, 세로 1 크기의 타일이 W×H 장 깔려 있다. 창고 출입문은 바깥 둘레에 있는 타일 가운데 정확히 하나에 붙어 있다. 창고 안에는 기둥이 몇 개 서 있다. 기둥이 하나도 없을 수도 있다.
옷장은 직육면체이고 가로가 2, 세로가 1이다. 가로가 2인 두 면 가운데 한 면에 문이 달려 있다. 문이 달린 면을 마주 보고 섰을 때 문은 그 면의 왼쪽 절반을 차지한다.
옷을 꺼내 오는 일은 로봇이 한다. 그래서 창고 입구에서 각 옷장의 문 앞까지 로봇이 지나갈 수 있는 경로가 있어야 한다. 로봇은 가로 1, 세로 1 크기이고, 타일에서 상하좌우로 인접한 타일로 움직인다. 옷장이나 기둥이 놓인 타일에는 올라갈 수 없다.
사장은 꼼꼼한 성격이라 옷장을 반드시 타일 두 장 위에 딱 맞게 놓으라고 지시했다. 그래서 옷장을 놓는 방법은 다음 네 가지뿐이다. C는 옷장 본체가 놓인 타일이고, X는 옷장 문을 열 수 있도록 아무것도 놓이면 안 되는 타일이다.
....
.CC.
.X..
....
....
..X.
.CC.
....
....
.XC.
..C.
....
....
.C..
.CX.
....
X 자리는 창고 안에 있어야 하고, 그 자리에 기둥도 다른 옷장도 없어야 하며, 입구에 붙은 타일에서 로봇이 그 자리까지 갈 수 있어야 한다.
창고에 놓을 수 있는 옷장 개수의 최댓값을 구하라.
입력
첫 줄에 테스트 케이스 개수 T가 주어진다.
각 테스트 케이스의 첫 줄에는 두 정수 H와 W가 공백을 사이에 두고 주어진다. H는 창고의 세로 길이이고 W는 가로 길이이다.
이어서 길이가 W인 문자열이 H줄 주어진다. i번째 줄의 j번째 문자는 타일 (i,j)의 상태를 나타낸다. 그 타일이 창고 입구에 붙어 있으면 "D", 기둥이 서 있으면 "X", 둘 다 아니면 "."이다. "D"는 테스트 케이스마다 정확히 한 번 나온다.
제한
- T≤100
- 1≤H≤5
- 1≤W≤5
출력
각 테스트 케이스마다 다음 형식으로 한 줄씩 출력한다.
Case #X: Y
X는 1부터 시작하는 테스트 케이스 번호이고, Y는 조건에 맞게 놓을 수 있는 옷장 개수의 최댓값이다.