Unique Paths in a Labyrinth

You are given a labyrinth represented as an n × m grid. Each cell is either empty (represented by .) or blocked (represented by #). Starting from the top-left cell at (0, 0), your task is to determine the number of unique paths to reach the bottom-right cell at (n-1, m-1) without visiting any cell more than once.

You can move in four directions: up, down, left, and right. If a cell is blocked or has already been visited in the current path, it cannot be used again. If there is no valid path, output 0.

This problem requires an efficient depth-first search (DFS) approach with proper backtracking to explore all possible paths.

inputFormat

The first line contains two space-separated integers, n and m, which represent the number of rows and columns in the grid respectively. The following n lines each contain a string of m characters where each character is either '.' (an open cell) or '#' (an obstacle).

outputFormat

Output a single integer representing the number of unique paths from the top-left cell to the bottom-right cell.## sample

3 3
...
.#.
...

2