P1746 Leaving Zhongshan Road

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

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?

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$.

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

For $20\%$ of the testdata, $1\leq n \le 100$. For $100\%$ of the testdata, $1\leq n \le 1000$. Translated by ChatGPT 5