Distinct Paths in a Grid

You are given a grid of size \(R \times C\) consisting of characters '.' and '#'. The character '.' denotes an empty cell, while '#' denotes an obstacle. Your task is to count the number of distinct paths from the top-left cell (i.e., cell \((0,0)\)) to the bottom-right cell (i.e., cell \((R-1,C-1)\)).

You can move in the four standard directions: up, down, left, and right. Each cell may only be visited once in any given path and you can only travel through cells that are empty ('.').

The problem can be mathematically described as finding the number of paths such that:

[ \text{Number of paths} = #{ p : p \text{ is a valid path from } (0,0) \text{ to } (R-1,C-1) }]

Consider the following examples:

• For a 3x3 grid:
  ...
.#.
...
  The number of distinct paths is 2.
• For a 3x3 grid with grid:
  ..#
.#.
..#
  The number of paths is 0.

Follow the input/output format as described below.

inputFormat

The input is given via standard input (stdin). The first line contains two integers, (R) and (C), representing the number of rows and columns respectively. Each of the following (R) lines contains a string of length (C). A character '.' represents an empty cell, and '#' represents an obstacle.

outputFormat

Print a single integer to standard output (stdout) representing the number of distinct paths from the top-left cell (0,0) to the bottom-right cell ((R-1,C-1)).## sample

3 3
...
.#.
...

2