Description
Problem brought to you by NTHU Amusement Programming Club.
Aoba works as a character designer at a game comapny Eaglesquat, and their new game Black Souls is almost finished.
As usual, things do not go too smoothly at the debugging stage. One report points out that, no matter how hard one might try, it is impossible to go to the final boss room. Aoba steals a peek at the map and suspects that the entrance to the final maze may not even be connected to the entrance to the final boss room.
The maze can be modelled as a 2D grid with size N∗M, with rows numbered from 1...N and column numbered from 1...M. The cell is numbered (i,j) if it is positioned at the ith row and jth column; and it is marked ‘1’ if player can walk on it or ‘0’ if not. The player can walk only in the up/down/left/right direction, and of course they can’t walk out of the maze.
The entrance to the maze (x1,y1) and the exit to the final boss room (x2,y2) are given, and their positions can not be modified. Two are connected if and only if the player can walk from the former to the latter.
If the entrance and exit are not connected, the crew would have to change the map structure to make them so. Since the release date is near, they have to do it quick and simple; only one horizontal or vertical corridor may be added, and they want the length to be minimized. A corridor is a series of consecutive cells on which the player can walk on.
Formally, an extra corridor that starts at (xi,yi) and ends at (xj,yj) may be added, if xi=xj or yi=yj, and the cost would be |xj−xi+1| if it is vertical or |yj−yi+1| if horizontal. The '0’s and '1’s between the endpoints do not affect the cost.
Since you are a CS student, Aoba knows you can write a program to find out the minimum length of the corridor that needs to be added. Ganbatte kudasai!
The sample testcase illustrated, orange cells denote the entrance and exit, while blue cells denote the corridor added.
Input
Each input file contains only one testcase. For each test case, there will be three lines and the maze map represented as a binary matrix:
The first line contains a pair of integers N M, denoting the size of the maze.
The second line contains a pair of integers x1 y1, which is the position of the entrance.
The third line contains a pair of integers x2 y2, which is the position of the exit.
The entrance and the exit are guaranteed to be at two different positions.
Following come N lines, each with a string of length M consisting of only 0 or 1, which is the maze as described in the problem. The row number is numbered from up to down, and the column number left to right. The numbers are 1-indexed.
2 <= N, M <= 500
Output
Output a single integer that is the minimum length of a corridor that needs to be built. If it is impossible to satisfy the requirements, output -1.