이사
면접 대비시간 제한8초메모리 제한1024 MB
벽이 아닌 칸을 겹치지 않는 L자 모양 카펫(3칸)으로 모두 덮는 방법의 수를 구합니다.
문제
최근 사정을 고려해 더 넓은 방으로 이사하기로 했다. 새 방의 평면도는 정사각형 칸을 세로 H칸, 가로 W칸으로 배열한 격자로 나타낼 수 있다. 각 칸은 벽이나 기둥처럼 들어갈 수 없는 칸(이하 벽 칸)이거나, 그 밖의 칸(이하 바닥 칸)이다.
새 방의 평면도를 SNS에 공유했더니, 친구가 집들이 선물로 L자형 타일 카펫을 많이 보내 왔다. 카펫 하나는 격자의 정확히 3칸을 덮는다. 친구 말로는 이 평면도라면 카펫을 격자에 맞춰 적절히 배치해서 서로 겹치지 않고 모든 바닥 칸을 덮을 수 있다고 한다.
실제로 카펫을 깔기 전에, 모든 바닥 칸을 덮는 배치가 몇 가지인지 알아보려고 한다. 조합을 셀 때 개별 카펫은 구별하지 않으며, 카펫에는 앞뒤 구별이 없다.
입력
첫 줄에 격자의 크기를 나타내는 정수 H, W (2 ≤ H, W ≤ 8)가 주어진다. 이어서 H줄에 걸쳐 각 줄은 W개의 문자로 이루어지며, 벽 칸은 '#', 바닥 칸은 '.'이다.
H W
a1,1 ... a1,W
...
aH,1 ... aH,W
격자는 다음 조건을 만족한다.
- 바닥 칸이 3개 이상 있다.
- 카펫이 겹치지 않고 모든 바닥 칸을 덮을 수 있는 배치가 1가지 이상 있다.
입력의 끝은 0 0인 줄이다. 데이터셋은 50개를 넘지 않는다.
출력
각 데이터셋에 대해 모든 바닥 칸이 L자형 카펫으로 덮이는 배치의 조합 수를 한 줄에 출력한다.