#C9870. Alice's Maze Escape
Alice's Maze Escape
Alice's Maze Escape
Alice is trapped in a maze represented by a grid. Some cells are open (denoted by .
) while others are blocked (denoted by #
). Starting at the top-left corner and needing to reach the bottom-right corner, Alice can only move up, down, left, or right. Both the start and end cells must be open (.
) for a valid path to exist.
Your task is to determine for each given grid whether there exists a path from the start to the finish. The problem may contain multiple datasets; each dataset is introduced by two positive integers H and W (representing the height and width of the grid respectively), followed by H lines describing the grid. The input terminates when a line with 0 0
is encountered. The answer for each dataset should be output as either Yes
(if such a path exists) or No
(if it does not).
The moves are allowed only in the four cardinal directions. A cell is considered reachable from another if it is adjacent in one of these directions.
Note: The problem may be represented with some mathematical notation. For example, if we let the grid be defined on indices \( (i,j) \) for \( 0 \le i < H \) and \( 0 \le j < W \), then a valid move from cell \( (i,j) \) is to any cell \( (i+1,j) \), \( (i-1,j) \), \( (i,j+1) \) or \( (i,j-1) \) provided that the cell lies within the grid and is not blocked.
inputFormat
The input is given via standard input (stdin) and consists of multiple datasets. Each dataset starts with a line containing two integers H and W (\(1 \le H, W\le \text{some limit}\)). Following this, there are H lines each containing a string of length W representing the grid, where a dot (.) represents an open cell and a hash (#) represents a blocked cell. The input terminates with a line containing 0 0
, which should not be processed.
outputFormat
For each dataset, output Yes
if there exists a path from the top-left corner to the bottom-right corner, and No
otherwise. Each answer should be printed on a separate line to the standard output (stdout).
1 1
.
0 0
Yes
</p>