Path to Exit in a Grid

This problem requires you to determine whether there is a path from the upper-left corner (cell (0,0)) to the lower-right corner (cell \( (h-1, w-1) \)) in a grid, avoiding obstacles. The grid is represented as a matrix of size \( h \times w \) where each cell is either 0 (empty) or 1 (obstacle). You can move in four directions: up, down, left, and right. Use a Breadth-First Search (BFS) algorithm to explore the grid.

Input Format: The first line contains two integers \( h \) and \( w \), indicating the number of rows and columns respectively. Following this, there are \( h \) lines each containing \( w \) space-separated integers (either 0 or 1) representing the grid.

Output Format: Output a single line: "YES" if there exists a valid path from the start to the exit, otherwise "NO".

inputFormat

The input begins with two integers \( h \) and \( w \) separated by a space. Then \( h \) lines follow, each containing \( w \) integers (0 or 1) separated by spaces.

Example:

3 3
0 1 0
0 0 1
1 0 0

outputFormat

Print "YES" if there is a path from the top-left corner to the bottom-right corner, otherwise print "NO".

3 3
0 1 0
0 0 1
1 0 0

YES