#C7783. Maze Path Finder
Maze Path Finder
Maze Path Finder
In this problem, you are given a maze represented as a 2D grid of integers, where a cell with value 1
indicates an open path and a cell with value 0
indicates a wall. You are also provided with a starting point and a destination point. Your task is to determine whether there exists a path from the starting point to the destination point by moving only in the four cardinal directions (up, down, left, and right).
The maze is defined by its dimensions n (number of rows) and m (number of columns), followed by the grid values, and finally the starting and destination coordinates. The coordinates are given in 0-indexed format.
The solution should output Yes if such a path exists, or No otherwise.
Mathematically, if the grid is represented as \(G\) where \(G[i][j]\) is either \(0\) or \(1\), and the starting point is \((s_x,s_y)\) and destination \((d_x,d_y)\), then you need to verify if there exists a sequence of moves such that:
\[ (s_x,s_y) \rightarrow (\ldots) \rightarrow (d_x,d_y) \quad \text{with} \quad G[i][j] = 1 \quad \forall (i,j) \text{ in the sequence.} \]inputFormat
The first line contains two integers n
and m
separated by a space, representing the number of rows and columns in the maze.
The next n
lines each contain m
integers (either 0
or 1
), representing each row of the grid.
The following line contains two integers representing the starting point coordinates (s_x
and s_y
).
The final line contains two integers representing the destination point coordinates (d_x
and d_y
).
outputFormat
Output a single line with the word Yes
if there exists a path from the starting point to the destination point; otherwise, output No
.
4 4
1 0 1 1
1 1 1 0
1 0 0 1
1 1 1 1
0 0
3 3
Yes