hzCPPOJ

走马观花

时间限制:  1 s      内存限制:   128 MB
提交:187     正确:88     分值:87

题目描述

给定一个大小为 n 行 m 列的棋盘,棋盘的左上角坐标为 (1, 1),右下角坐标为 (n, m)。在棋盘上的某个起始点 (x, y) 放置了一个中国象棋的马。马走“日”字,即可以横向移动两格纵向移动一格,或横向移动一格纵向移动两格。请你计算出马从起始点 (x, y) 出发,到达棋盘上任意一个点最少需要走几步。如果某个点无法到达,则输出 -1


问题分析:

题目要求我们计算中国象棋的马从初始位置(x, y)到达棋盘上所有其他点的最少步数,即求解最短路径问题

马走“日”字,即可以横向移动两格纵向移动一格,或横向移动一格纵向移动两格。棋盘的大小为n × m,其中1 ≤ n, m ≤ 400

算法选择:

为了求解最短路径问题,特别是这种网格上的移动问题,广度优先搜索(BFS)是最合适的算法。

BFS能够确保第一次访问某个点时,所用的步数就是最短步数。

BFS算法思路

  1. 初始化

    • 创建一个n × m的矩阵dist,初始值设为-1,表示未访问。

    • 将起始点(x, y)dist值设为0,并加入队列。

  2. BFS遍历

    • 从队列中取出当前点,检查其所有可能的8个移动方向。

    • 对于每个移动方向,计算新位置(nx, ny),如果新位置在棋盘内且未被访问过,则更新dist[nx][ny]为当前步数加1,并将新位置加入队列。

  3. 输出结果

    • 遍历dist矩阵,输出每个点的最短步数。



输入

输入只有一行,包含四个整数,分别为 nmxy,表示棋盘的行数、列数以及马的起始坐标。

输出

输出一个 n × m 的矩阵,矩阵中的每个元素表示马从起始点 (x, y) 到达该点的最少步数。如果无法到达,则对应位置输出 -1

数字之间用一个空格分隔。

样例

样例输入:
3 3 1 1
样例输出:
0 3 2 3 -1 1 2 1 4
样例输入:
6 9 1 1
样例输出:
0 3 2 3 2 3 4 5 4 3 4 1 2 3 4 3 4 5 2 1 4 3 2 3 4 5 4 3 2 3 2 3 4 3 4 5 2 3 2 3 4 3 4 5 4 3 4 3 4 3 4 5 4 5

提交人

lixun2017

来源/分类