Pathfinding in a Grid

You are given a grid represented by an $m \times n$ matrix $A$, where each element is either 0 or 1. A cell with a value of 0 is free, while a cell with a value of 1 is blocked. Your task is to determine whether there exists a valid path from the top-left corner (cell $A_{1,1}$) to the bottom-right corner (cell $A_{m,n}$). You can only move in two directions: right or down. Note that if the starting or ending cell is blocked (i.e. equal to 1), then no valid path exists.

Input Constraints:
The first line of input contains two integers $m$ and $n$, representing the number of rows and columns, respectively. The following $m$ lines each contain $n$ integers (either 0 or 1) separated by spaces, representing the grid.

Note: The allowed moves from any free cell $(i,j)$ are to the cell $(i, j+1)$ (right) or $(i+1, j)$ (down).

inputFormat

Input is given from standard input (stdin). The first line contains two integers $m$ and $n$, the number of rows and columns in the grid. Each of the next $m$ lines contains $n$ space-separated integers which are either 0 (free) or 1 (blocked).

outputFormat

Output to standard output (stdout) a single line containing either 'true' if there exists a valid path from the top-left corner to the bottom-right corner, or 'false' otherwise.## sample

3 3
0 0 0
0 1 0
0 0 0

true