Sleeping is a favorite of little bearBaby, because the wetness of Changsha in winter is too uncomfortable. One morning, little bearBaby accidentally overslept. The result of being late is very serious. You are the smartest artificial intelligence. Now little bearBaby asks you to help him figure out the minimum time it takes to reach the teaching building.
The school map is a grid of $n \times m$, each cell is either an open space or a building (cannot pass), and the bedroom of little bearBaby is at $(1,1)$ — — the starting point coordinates. The teaching building is at $(x, y)$——the target point coordinates, he can only go up, down, left or right, it takes $1$ minute for each step. The input data ensures that the teaching building is reachable.
The first line has two positive integers $n, m$ , separated by spaces $(1 ≤ n, m ≤ 100)$, $n$ for the
row, $m$ for the column.
Next there are two positive integers $x, y$, separated by spaces $(1 ≤ x ≤ n, 1 ≤ y ≤ m)$
indicating the coordinates of the teaching building.
Next is a map of $n$ rows and $m$ columns, $0$ indicate a open space and $1$ indicate a obstacles.
For each test case, output a single line containing an integer giving the minimum time little bearBaby takes to reach the teaching building, in minutes.
5 4 4 3 0 0 1 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 1
· \n · \n · · · \n · · · \n · · · \n · · · \n · · · \n
7
\n
For the input example, you could go like this:
$(1,1) \rightarrow (1,2) \rightarrow (2,2) \rightarrow (2,3) \rightarrow (2,4) \rightarrow (3,4) \rightarrow (4,4) \rightarrow (4,3)$,so the minimum time is $7$.
First grid in the upper left corner is $(1,1)$.