Classroom Pursuit

In a classroom represented by an \(n \times n\) matrix, each cell can be either empty (denoted by 0) or occupied by a desk (denoted by 1, which represents an obstacle). Two players are involved:

• Cuazyoxi holding Happybob's Pencil Case initially at cell \((x_1, y_1)\).
• Happybob initially at cell \((x_2, y_2)\).

Both players know the full layout of the classroom. They can only move to an adjacent cell (up, down, left, right) if that cell exists and is not an obstacle.

The game proceeds in seconds. In each second:

1. Cuazyoxi moves (or stays in place): he can move one step to an adjacent cell that is not an obstacle, or remain where he is.
2. Then Happybob moves. He is allowed to move once, twice, or not at all; each move is a step to an adjacent (non–obstacle) cell. After every move, both players know each other’s new position.

Both players play optimally: Cuazyoxi tries to delay being caught for as many seconds as possible, while Happybob tries to catch Cuazyoxi as quickly as possible. They are said to be caught when they are in the same cell.

It can be shown that if a path exists between the two positions, the outcome is determined by the shortest path distance \(d\) (measured in number of moves ignoring the turn order) from Cuazyoxi's starting cell to Happybob's starting cell. In each second, even though Cuazyoxi can try to increase the distance by 1, Happybob can decrease it by 2, so the catch will occur after exactly \(d\) seconds. (If \(d = 0\), they start together and the answer is 0.)

Your task is to compute \(d\), the minimal number of seconds such that, if both play optimally, Happybob is guaranteed to catch Cuazyoxi.

Note: The input positions are given in 1-indexed format. Use \(\LaTeX\) formatting for any formulas.

inputFormat

The first line contains a single integer \(n\) \( (1 \le n \le 1000)\) indicating the size of the classroom grid.

The second line contains four integers \(x_1\), \(y_1\), \(x_2\), \(y_2\) (\(1 \le x_1,y_1,x_2,y_2 \le n\)), representing the starting positions of Cuazyoxi and Happybob respectively.

The following \(n\) lines each contain \(n\) integers (each either 0 or 1) separated by spaces, describing the classroom grid. A 0 indicates an empty cell, and a 1 indicates an obstacle (desk). It is guaranteed that the starting cells for both players are empty (0).

outputFormat

Output a single integer: the minimal number of seconds after which Happybob is guaranteed to catch Cuazyoxi if both play optimally.

If the two positions are initially the same, output 0.

sample

3
1 1 3 3
0 0 0
0 0 0
0 0 0

4