1195 : 华容道

时间限制Time Limit
1 秒Sec
内存限制Memory Limit
128 兆MB
提交次数Submitted
301 次Times
通过次数Solved
48 次Times

题目描述Description

在一个n × m的棋盘上有n行m列共n × m个格子,其中有且只有一个格子是空白的,其余n × m − 1个格子上各有一个棋子. 每一步可以将空白的格子上、下、左、右相邻的格子上的棋子移动到空白格子上.

我们需要计算将某个位置的棋子移动到指定位置的最小步数.

输入格式Input

包含不超过1000组测试数据.

每组测试数据包括8个整数n, m, x, y, r1, c1, r2, c2,表示棋盘的大小为n × m,第x行y列的格子是空白的,需要将第r1行c1列的棋子移动到第r2行c2列.

2 ≤ n ≤ 108,2 ≤ m ≤ 108.

输出格式Output

输出将棋子移动到指定位置的最小步数.

样例Sample

出题Author

Staginner