게임판 덮기
문제 정보
-
- 문제 ID
- 시간 제한
- 메모리 제한
- 제출 횟수
- 정답 횟수 (비율)
-
- BOARDCOVER
- 2000ms
- 65536kb
- 11760
- 5641 (47%)
-
- 출처
- 분류
문제
H*W 크기의 게임판이 있습니다. 게임판은 검은 칸과 흰 칸으로 구성된 격자 모양을 하고 있는데 이 중 모든 흰 칸을 3칸짜리 L자 모양의 블록으로 덮고 싶습니다. 이 때 블록들은 자유롭게 회전해서 놓을 수 있지만, 서로 겹치거나, 검은 칸을 덮거나, 게임판 밖으로 나가서는 안 됩니다. 위 그림은 한 게임판과 이를 덮는 방법을 보여줍니다.
게임판이 주어질 때 이를 덮는 방법의 수를 계산하는 프로그램을 작성하세요.
입력
력의 첫 줄에는 테스트 케이스의 수 C (C <= 30) 가 주어집니다. 각 테스트 케이스의 첫 줄에는 2개의 정수 H, W (1 <= H,W <= 20) 가 주어집니다. 다음 H 줄에 각 W 글자로 게임판의 모양이 주어집니다. #
은 검은 칸, .
는 흰 칸을 나타냅니다. 입력에 주어지는 게임판에 있는 흰 칸의 수는 50 을 넘지 않습니다.
출력
한 줄에 하나씩 흰 칸을 모두 덮는 방법의 수를 출력합니다.
예제 입력
3 3 7 #.....# #.....# ##...## 3 7 #.....# #.....# ##..### 8 10 ########## #........# #........# #........# #........# #........# #........# ##########
예제 출력
0 2 1514
노트