小明的游戏

题目描述

小明最近喜欢玩一个游戏。给定一个$n \times m$的棋盘,上面有两种格子`#`和`@`。游戏的规则很简单:给定一个起始位置和一个目标位置,小明每一步能向上,下,左,右四个方向移动一格。如果移动到同一类型的格子,则费用是$0$,否则费用是$1$。请编程计算从起始位置移动到目标位置的最小花费。

输入输出格式

输入格式


输入文件有多组数据。 输入第一行包含两个整数$n$,$m$,分别表示棋盘的行数和列数。 输入接下来的$n$行,每一行有$m$个格子(使用`#`或者`@`表示)。 输入接下来一行有四个整数$x_1, y_1, x_2, y_2$,分别为起始位置和目标位置。 当输入$n$,$m$均为$0$时,表示输入结束。

输出格式


对于每组数据,输出从起始位置到目标位置的最小花费。每一组数据独占一行。

输入输出样例

输入样例 #1

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

输出样例 #1

2
0

说明

对于20%的数据满足:$1 \le n, m \le 10$。 对于40%的数据满足:$1 \le n, m \le 300$。 对于100%的数据满足:$1 \le n, m \le 500$。