Counting Hamiltonian Cycles on a Grid with Obstacles

You are given an n × m grid. Each cell is either available (denoted by '.') or blocked (denoted by '#'). Every available cell must be part of a wiring and the wiring in the grid must form a single closed loop that passes through every available cell exactly once. Two cells are considered adjacent if they share a common edge (up, down, left, right). In other words, you are asked to count the number of Hamiltonian cycles on the induced subgrid of available cells.

Important:

• The cycle must start and end at the same cell and use every available cell exactly once.
• During the search, the starting cell should be fixed to avoid counting duplicate cycles.
• You can assume that the grid dimensions are small enough for a backtracking solution to pass.

In mathematical notation, if the total number of available cells is T, then you are to count the number of ways to choose a cycle such that for the sequence of cells v₀,v₁,…,v_T-1 we have

\( v_0 = v_{T} \) and for every \( 0 \le i < T \), \( v_i \) and \( v_{i+1} \) are adjacent.

inputFormat

The first line contains two integers \( n \) and \( m \) (the number of rows and columns, respectively). Each of the following \( n \) lines contains a string of length \( m \) consisting of characters . (available cell) and # (blocked cell).

outputFormat

Output a single integer representing the number of ways to lay the wiring so that all available cells are part of a single closed loop (Hamiltonian cycle).

sample

2 2
..
..

1