Path Existence in a Binary Grid

You are given a grid of size \(m \times n\) consisting of 0s and 1s, where 0 represents a free cell and 1 represents an obstacle. Starting from the top-left corner (cell (0, 0)), determine if there exists a valid path to the bottom-right corner (cell (m-1, n-1)). You can move in the four cardinal directions: up, down, left, or right. Diagonal moves are not allowed.

Formally, let \(A\) be the grid where \(A_{ij}\) is 0 if the cell is passable and 1 if it is blocked. You need to decide whether there exists a sequence of moves from \((0,0)\) to \((m-1,n-1)\) without stepping into a cell with an obstacle.

inputFormat

The first line contains two integers \(m\) and \(n\) representing the number of rows and columns, respectively. The following \(m\) lines each contain \(n\) space-separated integers (each either 0 or 1) representing the grid.

outputFormat

Output a single line containing either True or False, indicating whether a valid path exists from the top-left corner to the bottom-right corner.

4 4
0 1 0 0
0 0 1 0
1 0 0 0
0 0 0 0

True