Background

The final chapter of “A Story of Love and Sorrow III · shopping”.

Problem Description

After shopping, Aiyuchou plans to take a bus to leave Zhongshan Road. He is at $x_1,y_1$, and the station is at $x_2,y_2$. You are given an $n \times n(n \le 1000)$ map, where $0$ represents road and $1$ represents shop (cannot pass through shops). Aiyuchou can move only vertically or horizontally along roads. To save time, he wants the shortest distance to the destination (the distance between two adjacent coordinates is $1$). Can you help him?

Input Format

Line $1$ contains an integer $n$.

Lines $2$ to $n+1$: the entire map description ($0$ represents road, $1$ represents shop; note there are no spaces between numbers).

Line $n+2$: four integers $x_1,y_1,x_2,y_2$.

Output Format

Only $1$ line, the shortest distance to the destination.

3
001
101
100
1 1 3 3

4

Hint

For $20\%$ of the testdata, $1\leq n \le 100$.

For $100\%$ of the testdata, $1\leq n \le 1000$.

Translated by ChatGPT 5