#P13008. 跳马问题

跳马问题

题目背景

有一个 n×mn \times m 的棋盘,棋盘左下角坐标为 (0,0)(0,0),右上角坐标为 (n,m)(n,m)

题目描述

马从起始坐标点 (x1,y1)(x_1,y_1) 出发,只能在棋盘内跳“日”字(参照象棋中的马),问至少需要多少步才能跳到目标坐标点 (x2,y2)(x_2,y_2)?输出任意一种最少步数的跳跃方案。如果最少步数方案不唯一,仅需输出任意一种即可

输入格式

一共三行。

11 行是两个正整数 n,mn,m;第 22 行是两个非负整数 x1,y1x_1,y_1;第 33 行是两个非负整数 x2,y2x_2,y_2

相邻整数间用一个空格隔开。

输出格式

一共 22 行。

11 行是一个正整数,就是题目所求的最少跳跃次数。

22 行是一组用一个空格隔开的形如 (x,y) 的坐标点,就是一种最少步数的跳跃方案依次经历过的坐标点。

输入输出样例

10 10 0 0 5 10
5
(0,0) (1,2) (2,4) (3,6) (4,8) (5,10) 

说明/提示

👀️ 对于100%100\% 的数据,1n,m10001 \leq n,m\leq 10000x1,x2n0 \leq x_1,x_2 \leq n0y1,y2m0 \leq y_1,y_2 \leq m,起始坐标点与目标坐标点不相同。