1015: 湖南省第十八届大学生计算机程序设计竞赛(HNCPC2022) - Semilive

开始 Start
0000-00-0000:00:00UTC+0
结束 End
0000-00-0000:00:00UTC+0
当前 Now
0000-00-0000:00:00UTC+0
状态 Status
加载中Loading
类型 Type
开放Public
榜单 Rank
加载中Loading
公告 Announcement
暂无公告No announcement

G : 华容道

时间限制Time Limit
1 秒Sec
内存限制Memory Limit
128 兆MB
提交次数Submitted
117 次Times
通过次数Solved
22 次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