Maze Path Existence

You are given a maze represented by an n × m grid. Each cell is either an open cell (denoted by .) or a wall (denoted by #). Your task is to determine whether there exists a valid path from the top-left corner (cell (1,1)) to the bottom-right corner (cell (n,m)). You may move in four directions: up, down, left, or right. You cannot move diagonally, through walls, or outside the maze boundaries.

The problem can be mathematically represented as follows:

Let the maze be represented by a matrix \(A\) of size \(n \times m\) where \[ A_{ij} = \begin{cases} '.' & \text{if the cell is open},\\ '#' & \text{if the cell is a wall}. \end{cases} \]

Define the starting cell as \(A_{11}\) and the target cell as \(A_{nm}\). A move from cell \(A_{ij}\) is allowed to any adjacent cell \(A_{i'j'}\) if \(|i-i'| + |j-j'| = 1\) and \(A_{i'j'} = '.'\). The task is to decide if there is a sequence of moves that leads from \(A_{11}\) to \(A_{nm}\).

inputFormat

The first line of input contains two space-separated integers n and m, representing the number of rows and columns of the maze respectively.

This is followed by n lines, each containing a string of m characters. Each character is either . (an open cell) or # (a wall).

You can assume that n, m ≥ 1.

outputFormat

Output a single line. Print Path Exists if there is at least one valid path from the top-left corner to the bottom-right corner; otherwise, print No Path.

3 3
.#.
...
.#.

Path Exists