Description

Xiao Ming recently enjoys playing a game. Given an $n \times m$ board with two types of cells # and @. The rules are simple: given a starting position and a target position, each step Xiao Ming can move one cell in one of the four directions: up, down, left, or right. If he moves onto a cell of the same type, the cost is $0$; otherwise, the cost is $1$. Write a program to compute the minimum cost to move from the starting position to the target position.

Input Format

The input contains multiple test cases.
The first line of each test case contains two integers $n$, $m$, the number of rows and columns of the board.
The next $n$ lines each contain $m$ cells (denoted by # or @).
The next line contains four integers $x_1, y_1, x_2, y_2$, the starting position and the target position, respectively.
The input ends when both $n$ and $m$ are $0$.

Output Format

For each test case, output the minimum cost from the starting position to the target position. Print one result per line.

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

2
0

Hint

• For 20% of the testdata: $1 \le n, m \le 10$.
• For 40% of the testdata: $1 \le n, m \le 300$.
• For 100% of the testdata: $1 \le n, m \le 500$.

Translated by ChatGPT 5