Taco Navigator: Shortest Path in a City Grid

You are given a grid representing a city map. Each cell in the grid is either 0 representing an open intersection or 1 representing a blocked intersection. You are also provided with the starting intersection coordinates and the accident site coordinates. Your task is to find the shortest path, measured in the number of intersections traversed, from the start to the accident site.

The grid is indexed starting from 1. You may move in four directions: up, down, left, and right. If there is no valid path to reach the accident site, output -1.

Note: The answer is based on the number of intersections traversed (each move counts as 1). When the start coincides with the accident site, the answer is 0.

The problem can be formulated as follows:

Find the minimum number of steps required to go from \( (s_x, s_y) \) to \( (a_x, a_y) \) in an \( n \times m \) grid where only cells with value 0 can be traversed.

inputFormat

The input is read from standard input (stdin) and has the following format:

n m
sx sy
ax ay
row1
row2
...
rown

Where:

• \(n\) and \(m\) represent the number of rows and columns of the grid respectively.
• \(s_x, s_y\) are the starting intersection coordinates.
• \(a_x, a_y\) are the accident site coordinates.
• Each of the next \(n\) lines contains \(m\) integers separated by spaces (each either 0 or 1) representing the grid map.

outputFormat

Output a single integer on a line by itself: the minimum number of intersections traversed to reach the accident site from the starting point. If no path exists, print -1.

## sample

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

8