Background

ural 1519.

An example problem from Chen Danqi’s article Dynamic Programming Problems Based on Connectivity State Compression.

Problem Description

Given an $n\times m$ grid, some cells cannot be used to place lines, and all other cells must be used to place lines, forming one closed loop. How many different ways are there to place the lines?

Input Format

The first line contains two integers, representing $n$ and $m$.

From the second line to the $(n+1)$-th line, each line contains a string of length $m$ consisting only of * and ., where * means you cannot place lines in this cell, and . means you must place lines in this cell.

Output Format

Output one line with one integer, representing the total number of valid ways.

4 4
**..
....
....
....

2

4 4
....
....
....
....

6

Hint

Constraints

• For $100\%$ of the testdata, $2\le n,m\le 12$.

Translated by ChatGPT 5