Nearest Parking Spot

In a parking lot represented as a two-dimensional grid, each cell is either occupied (represented by 1) or available (represented by 0). The entrance to the parking lot is at the top‐left corner, i.e. cell \((0,0)\). From the entrance, you can move horizontally or vertically. Your task is to find the nearest available parking spot (a cell with value 0) using the shortest path. If multiple spots are at the same minimum distance, choose the one that appears first in row-major order (i.e. top-to-bottom, left-to-right). If no available spot exists, output -1.

inputFormat

The input starts with a line containing two integers \(R\) and \(C\) (\(1 \le R, C \le 1000\)), representing the number of rows and columns in the parking lot grid. This is followed by \(R\) lines, each containing \(C\) integers (each either 0 or 1) separated by spaces, representing the grid.

outputFormat

If an available parking spot is found, print two integers separated by a space: the row and the column indices (0-indexed) of the spot. Otherwise, print -1.

3 4
1 1 0 1
1 0 0 1
1 1 1 1

0 2