LG#P1443. 马的遍历

马的遍历

题目描述

\hspace{15pt}给定一个 n×mn\times m 的棋盘,行、列均从 11 开始编号,一匹马最初位于 (x,y)(x,y)。

\hspace{15pt}马每次可向一个方向移动两格,再沿垂直方向移动一格,即坐标变化为 (±1,±2)(\pm1,\pm2) 或 (±2,±1)(\pm2,\pm1),共有八种可能。棋盘上没有障碍,但马不能走出棋盘。

\hspace{15pt}请计算从起点到每个格子的最少步数。

输入格式

\hspace{15pt}在一行上输入四个整数 $n,m,x,y\left(1\leqq n,m\leqq400;\ 1\leqq x\leqq n;\ 1\leqq y\leqq m\right)$。

输出格式

\hspace{15pt}输出 nn 行,每行 mm 个整数,相邻整数以空格分隔,表示到达对应格子的最少步数。不能到达的格子输出 −1-1,起点输出 00。

测试样例

3 3 1 1
0 3 2    
3 -1 1    
2 1 4

样例 1 解释

\hspace{15pt}从 (1,1)(1,1) 一步可到达 (2,3)(2,3) 和 (3,2)(3,2)。中心 (2,2)(2,2) 无法到达,因此输出 −1-1。到 (3,3)(3,3) 的最短路线需要 44 步,例如 (1,1)→(2,3)→(3,1)→(1,2)→(3,3)(1,1)\to(2,3)\to(3,1)\to(1,2)\to(3,3)。

1 3 1 2
-1 0 -1