健美羊（bodyshape）

问题背景

小 D 是一只追求健美身材的喜羊羊。

问题描述

羊的身材有两个关键指标：羊角的长度 $x$ 和羊毛量 $y$。$x,y$ 是正整数，取值范围分别是 $1\ldots n$ 和 $1\ldots m$。

小 D 目前的角长是 $x_1$，毛量是 $y_1$，他想通过健美塑形达到咩咩国公认的完美身材指标：角长 $x_2$ 和毛量 $y_2$。小 D 可以通过以下两类训练方式改变身材指标：

• 打球：每天使角的长度增加或减少 $1$，但不能超出 $1\ldots n$ 范围。
• 弹琴：每天使羊毛量增加或减少 $1$，但不能超出 $1\ldots m$ 范围。

咩咩国卫健委通过科学研究，发现某些特定身材指标是不健康的。小 D 不希望任何时刻处于任何不健康的身材指标。保证 $(x_1,y_1)$ 和 $(x_2,y_2)$ 一定是健康的。

小 D 连续任意天都打球，或连续任意天都弹琴，都不会产生任何代价；但每次从打球切换到弹琴，或从弹琴切换到打球，都会产生 $1$ 单位的代价。求达到目标状态 $(x_2,y_2)$ 的最小总代价。

输入格式

从文件 bodyshape.in 中读取数据。

第一行两个正整数 $n,m$。

后面 $n$ 行给出一个 $n\times m$ 的 01 矩阵，其中第 $x$ 行第 $y$ 列为 0 表示 $(x,y)$ 这种身材是健康的；为 1 表示 $(x,y)$ 这种身材是不健康的。保证第 $x_1$ 行第 $y_1$ 列和第 $x_2$ 行第 $y_2$ 列一定是 0。

最后一行四个正整数 $x_1,y_1,x_2,y_2$。

输出格式

输出到文件 bodyshape.out。

输出一个整数，表示从 $(x_1,y_1)$ 训练到 $(x_2,y_2)$ 的最小代价。如果做不到则输出 -1。

样例 1

5 7
1 0 0 0 0 1 0
0 0 1 0 1 0 0
0 0 0 0 1 0 1
0 1 1 0 0 0 0
0 0 0 0 1 1 0
1 3 1 7

5

样例 1 解释

一种达到最小代价的训练过程为：

$(1,3)\rightarrow(1,4)$

$\Rightarrow(2,4)\Rightarrow(3,4)\Rightarrow(4,4)$

$\rightarrow(4,5)\rightarrow(4,6)$

$\Rightarrow(3,6)\Rightarrow(2,6)$

$\rightarrow(2,7)$

$\Rightarrow(1,7)$

单箭头表示弹琴，双箭头表示打球；单双箭头切换一共发生五次。

数据规模与约定

• 30% 的数据，$n,m\leq 5$。
• 70% 的数据，$n,m\leq 100$。
• 100% 的数据，$1\leq n,m\leq 2000$，$1\leq x_1,x_2\leq n$，$1\leq y_1,y_2\leq m$。

所有测试点时限均为 1 秒，内存限制均为 512 MiB。

文件读写说明

必须使用文件读写。在 main 函数开头加入：

freopen("bodyshape.in", "r", stdin);
freopen("bodyshape.out", "w", stdout);