Path Existence in a Binary Grid

You are given an N × N grid consisting solely of characters '0' and '1'. Your task is to determine whether there exists a path from the top-left corner of the grid (0, 0) to the bottom-right corner (N-1, N-1), moving only to adjacent cells (up, down, left, or right) that contain the character '1'.

Note: Both the starting cell and the destination cell must contain '1'; otherwise, the answer is NO. The movement is only allowed if the neighboring cell is within grid bounds and has the value '1'.

This problem can be modeled as a path search in a grid. One common approach is to use depth-first search (DFS) or breadth-first search (BFS) to explore all possible moves. In mathematical terms, you can think of the grid as a graph where each cell with '1' is a node. Two nodes are connected if they are adjacent (e.g. up, down, left, or right). Formally, if we denote the grid by \(G\) with \(G[i][j]\) representing the character in the cell, the allowed moves are defined by:

[ (x, y) \to (x+1, y),\quad (x, y) \to (x-1, y),\quad (x, y) \to (x, y+1),\quad (x, y) \to (x, y-1) ]

Your task is to output YES if such a path exists; otherwise, output NO.

inputFormat

The input is read from standard input (stdin) and is formatted as follows:

1. The first line contains an integer N denoting the size of the grid.
2. The following N lines each contain a string of length N consisting of the characters '0' and '1'.

outputFormat

Output a single line to standard output (stdout): YES if there exists a path from the top-left corner to the bottom-right corner moving only through cells containing '1', otherwise output NO.

3
110
010
011

YES