LG#P1443. 马的遍历
马的遍历
题目描述
给定一个 的棋盘,行、列均从 开始编号,一匹马最初位于 。
马每次可向一个方向移动两格,再沿垂直方向移动一格,即坐标变化为 或 ,共有八种可能。棋盘上没有障碍,但马不能走出棋盘。
请计算从起点到每个格子的最少步数。
输入格式
在一行上输入四个整数 $n,m,x,y\left(1\leqq n,m\leqq400;\ 1\leqq x\leqq n;\ 1\leqq y\leqq m\right)$。
输出格式
输出 行,每行 个整数,相邻整数以空格分隔,表示到达对应格子的最少步数。不能到达的格子输出 ,起点输出 。
测试样例
3 3 1 1
0 3 2
3 -1 1
2 1 4
样例 1 解释
从 一步可到达 和 。中心 无法到达,因此输出 。到 的最短路线需要 步,例如 。
1 3 1 2
-1 0 -1