cinador   3년 전

문제

당신은 여러 사정으로 인해 더 넓은 방으로 이사를 했다. 새로운 방의 구조는 H행 W열의 정사각형 칸들로 이루어진 격자로 나타낼 수 있다. 격자의 각 칸은 벽이나 기둥같이 들어갈 수 없는 칸(이하, '벽 칸'이라 한다)과 그 이외의 칸(이하, '바닥 칸'이라 한다)으로 나누어진다.

당신이 새로운 방의 모습을 SNS에 공유하자, 당신의 친구 중 하나가 이사 선물로 3개의 칸을 차지하는 ㄴ자형 타일 카페트를 여러 개 보내왔다. 그 친구의 말로는 방의 구조를 봤을 때, ㄴ자형 타일 카페트들을 적당히 회전하거나 뒤집어서 바닥 칸에 맞게 놓으면, 타일 카페트들이 서로 겹치지 않으면서 바닥 칸을 모두 덮을 수 있다고 한다.

당신은 실제로 타일 카페트를 놓기 전에, 타일 카페트로 겹치지 않게 바닥 칸을 모두 덮는 방법이 몇 가지인지 알려고 한다. 이 때, 각 타일 카페트 및 타일 카페트의 앞뒷면은 서로 구별하지 않는다.

ㅤ

입력

입력은 최대 50개의 테스트 케이스로 이루어져 있으며, 각 테스트 케이스는 다음과 같은 형식을 갖는다.

preview

첫 번째 줄은 방의 크기를 나타내는 2개의 양의 정수 H, W (2 ≤ H, W ≤ 8) 가 주어진다. 다음 H개의 각 줄에는 W개의 문자가 주어지며, 벽 칸을 나타내는 '#'과 바닥 칸을 나타내는 '.' 으로 이루어져 있다. 

 입력으로 주어지는 방의 구조는 다음을 만족한다.

  • 바닥 칸이 3개 이상이다.
  • 타일 카페트로 겹치지 않게 바닥 칸을 모두 덮는 방법은 1가지 이상 존재한다.

입력의 마지막에는 두 개의 0이 주어진다.

ㅤ

 출력

각 테스트 케이스에 대해, ㄴ자형 타일 카페트로 겹치지 않게 바닥 칸을 모두 덮는 방법의 수를 한 줄에 하나씩 출력한다.

댓글을 작성하려면 로그인해야 합니다.