Nearest Zero in a 3x3 Grid

You are given a fixed 3×3 grid where the rows and columns are indexed from 0 to 2. Each cell in the grid contains either a 0 or a 1. You are also given a starting coordinate (r, c). Your task is to determine the minimum number of moves required to reach any cell containing a 0 from the starting cell. You can move in four directions: up, down, left, or right (no diagonal moves are allowed).

The problem can be viewed as finding the shortest path in an unweighted grid. Formally, if you denote the current cell by \((i, j)\) and a neighboring cell by \((i+di, j+dj)\) where \(di, dj\) can be either -1, 0, or 1 (but not both non-zero simultaneously), then the distance increases by 1 for each move. The formula for Manhattan distance (when a direct path exists) is given by: \[ distance = |i_1 - i_2| + |j_1 - j_2| \] However, because obstacles might force you to take longer routes, you should use a breadth-first search (BFS) to determine the shortest path.

If the starting cell is already 0, the answer is 0. If no cell with 0 can be reached, output -1.

inputFormat

The input is provided via standard input (stdin) and consists of 4 lines:

1. The first three lines each contain three integers separated by a space, representing the rows of the grid.
2. The fourth line contains two integers separated by a space, representing the starting coordinates (row and column).

For example:

1 1 1
1 0 1
1 1 1
0 0

outputFormat

Output a single integer to standard output (stdout) which represents the minimum number of moves required to reach any cell with a 0. If no such cell is reachable, output -1.

1 1 1
1 0 1
1 1 1
0 0

2