中山市选[2009]小明的游戏

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

请编程计算从起始位置移动到目标位置的最小花费。

输入格式

输入文件有多组数据。

每组数据第一行包含两个整数 $n$、$m$，分别表示棋盘的行数和列数。

接下来的 $n$ 行，每一行有 $m$ 个格子（使用 # 或者 @ 表示）。

接下来一行有四个整数 $x_1, y_1, x_2, y_2$，分别为起始位置和目标位置。

当输入的 $n$、$m$ 均为 $0$ 时，表示输入结束。

输出格式

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

样例输入

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

样例输出

2
0

样例解释

第一组棋盘的两行为 @# 和 #@，从 $(0,0)$ 走到 $(1,1)$ 无论怎么走都要经过两次类型变化，最小花费为 $2$。

第二组棋盘的两行为 @@ 和 @#，从 $(0,1)$ 经 $(0,0)$ 走到 $(1,0)$，沿途三个格子都是 @，最小花费为 $0$。

数据范围

• 对于 $100\%$ 的数据，$1\le n, m\le 500$。

来源与许可

本题为中山市选 2009 试题「小明的游戏」，题面与测试数据整理自 BZOJ 2464。

样例 1

输入

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

输出

2
0