22046_Max'sgame

Max is lately playing a game. Given a n*m board, there are only two types of grid on it: # and @. And the rule is simple: Given a start position to Max, and Max can move to four direction for each step, up, down, left, right. When moving between two same type grids, it costs zero, otherwise, it costs one. Now, Max gets two different positions on the board: the start position and the target position, he wants to know how many costs he need to spend to achieve the game at least.

Input contains multiple test data sets.

For each data set, first comes two integers in one line: n, m ( 1 ≤ n, m ≤ 500 ), stands for the number of row and the number of column of the board. Then comes n lines with m grid characters per each. The characters are only @ or #. Then four integers in one line follow: x₁, y₁, x₂, y₂ ( 0 ≤ x₁, x₂ < n,   0 ≤ y₁, y₂ < m ) which is the start position and the end position correspondingly.

Input is terminated by EOF.

For each test data set, one output data set should be generated as follow:

Generates one line containing one integer which indicates the minimum cost Max need to take for the game.

2 2
@#
#@
0 0 1 1
2 2
@@
@#
0 1 1 0

2
0