Taco: City Grid Navigation

In this problem, you are given a square grid representing a city map. Each cell in the grid is either an open road (denoted by 0) or a road under construction (denoted by 1). A car starts at the top‐left corner (cell (1,1)) and must reach the bottom-right corner (cell (n,n)). The car can move in four directions: up, down, left, and right. Your task is to determine whether there exists a valid path from the start to the destination.

The movement is subject to the following rules:

• You cannot move out of the grid.
• You cannot pass through cells with a value of 1.

The answer should be output as Yes if a valid path exists and No otherwise.

Note: The grid is guaranteed to be square, and the first line of input contains the integer n (\(n \geq 1\)), representing the number of rows (and columns). The subsequent n lines represent the grid rows with n space-separated integers each.

inputFormat

The first line contains an integer (n) ((1 \leq n \leq 1000)), indicating the size of the grid. The next (n) lines each contain (n) space-separated integers (either 0 or 1), representing the grid where 0 indicates an open road and 1 indicates a road under construction.

outputFormat

Output a single line with the string Yes if there exists a path from the top-left corner to the bottom-right corner, or No otherwise.## sample

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

Yes