Robot Docking Station Shortest Path

A robot is placed on an n × n grid where each cell is either free (0) or contains an obstacle (1). The robot’s goal is to reach the docking station located at cell (0, 0) using the minimum number of steps. In one move, the robot can move up, down, left, or right to an adjacent cell provided that the cell is within the grid and free of obstacles.

If the docking station is unreachable, return -1.

Input Constraints:

• n (grid size): 2 \le n \le 50
• x, y: starting coordinates of the robot.
• Grid: An n × n matrix where each element is either 0 (free) or 1 (obstacle).

Example: For a grid of size 4 with starting position at (3, 3):

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

The shortest path from (3,3) to (0,0) consists of 6 moves. The minimum number of steps is therefore 6.

The problem can be modeled using a Breadth First Search (BFS) algorithm. The number of moves is essentially the shortest path length from the starting cell to cell (0, 0) on the grid. In mathematical terms, if there were no obstacles, the shortest distance would be given by the Manhattan distance: $$d = |x - 0| + |y - 0|.$$ However, obstacles may force a longer path or render the docking station unreachable.

inputFormat

The input is read from stdin and is in the following format:

 n x y
 row1_element1 row1_element2 ... row1_elementn
 row2_element1 row2_element2 ... row2_elementn
 ...
 rown_element1 rown_element2 ... rown_elementn

Where:

• n is the size of the grid.
• x and y are the starting coordinates of the robot.
• The following n lines specify the grid rows, each containing n space-separated integers (either 0 or 1).

outputFormat

Output a single integer to stdout which is the minimum number of steps needed to reach the docking station at cell (0, 0). If the docking station is unreachable, output -1.

## sample

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

6