문제 설명
H*W 크기의 게임판이 있습니다. 게임판은 검은 칸과 흰 칸으로 구성된 격자 모양을 하고 있습니다. 주어진 게임판의 흰 칸을 3칸 짜리 L자 모양의 블록으로 덮고 싶습니다. 이때 블록은 자유롭게 회전하여 높을 수 있지만, 서로 겹치거나 검은 칸을 덮거나 게임판 밖으로 나가서는 안 됩니다. 다음의 예시입니다.
게임판이 주어질 때 이를 덮는 방법의 수를 찾아주세요.
https://www.algospot.com/judge/problem/read/BOARDCOVER
입력 설명
첫 줄에는 테스트케이스의 수 T(1<=T<=30)가 주어집니다. 각 테스트케이스의 첫 줄에는 2개의 정수 H와 W(1<=H, W<=20)가 주어집니다. 다음 H 줄에 각 W 글자로 게임판의 모양이 주어집니다. #은 검은 칸, .은 흰 칸을 나타냅니다. 입력에 주어지는 게임판에 있는 흰 칸의 수는 50을 넘지 않습니다.
출력 설명
주어진 게임판의 흰 칸을 모두 덮는 방법의 수를 출력합니다.
3
3 7
#.....#
#.....#
##...##
3 7
#.....#
#.....#
##..###
8 10
##########
#........#
#........#
#........#
#........#
#........#
#........#
##########