Shortest Path in a City Grid

After shopping, the famous "Love and Sorrow" wants to catch a bus from Zhongshan Road. He is currently at position \( (x_1, y_1) \) and the bus station is located at \( (x_2, y_2) \). You are given an \( n \times n \) grid (with \( n \le 1000 \)), where each cell is either a road or a shop. A cell with value 0 represents a road and 1 represents a shop (and shops cannot be passed through). The travel is only allowed in vertical or horizontal directions (each step between adjacent cells is of length 1). Find the shortest distance from the starting point to the destination. If the destination cannot be reached, output -1.

Note: The coordinates are zero-indexed.

The distance is defined as the minimum number of moves from \( (x_1, y_1) \) to \( (x_2, y_2) \) over cells with value 0, moving only up, down, left, or right.

inputFormat

The first line contains an integer \( n \) denoting the size of the grid.

The second line contains four integers \( x_1\), \( y_1\), \( x_2\), and \( y_2 \) which represent the starting and destination coordinates respectively (0-indexed).

The next \( n \) lines each contain \( n \) space-separated integers (either 0 or 1) describing the grid. A 0 represents a road, and a 1 represents a shop.

outputFormat

Output a single integer which is the shortest distance from the starting point to the destination. If there is no such path, output -1.

sample

5
0 0 4 4
0 0 0 0 0
1 1 1 0 0
0 0 0 0 1
0 1 1 0 0
0 0 0 0 0

8