Path in a Binary Grid

Given a grid of zeros and ones with dimensions (R \times C), determine whether there is a path from any cell in the top row to any cell in the bottom row. You may move in any of the 8 possible directions (horizontal, vertical, or diagonal). Formally, a move from a cell at ((i, j)) can be made to ((i+dx, j+dy)) where (dx, dy \in {-1, 0, 1}) and not both are zero. If such a path exists using only cells with value 1, output 1; otherwise, output 0. This problem tests your ability to traverse grids and perform depth-first search (DFS) in a multi-directional context.

inputFormat

The input is given via standard input (stdin). The first line contains two integers, (R) and (C), separated by a space, representing the number of rows and columns of the grid. This is followed by (R) lines, each containing (C) integers (either 0 or 1), separated by spaces, representing the grid.

outputFormat

Output a single integer, either 1 or 0, to standard output (stdout). Print 1 if there is a path from the top row to the bottom row following the allowed moves, and 0 if no such path exists.## sample

5 5
1 0 0 1 0
1 1 0 0 0
0 1 1 1 0
0 0 0 1 0
0 0 1 1 1

1