洛谷 P1443 马的遍历

洛谷 /P1443 马的遍历 题目描述

有一个 n times mn×m 的棋盘，在某个点 (x, y)(x,y) 上有一个马，要求你计算出马到达棋盘上任意一个点最少要走几步。

输入格式

输入只有一行四个整数，分别为 n, m, x, yn,m,x,y。

输出格式

一个 n times mn×m 的矩阵，代表马到达某个点最少要走几步（左对齐，宽 55 格，不能到达则输出 -1−1）。

输入输出样例

输入 #1复制

3 3 1 1

输出 #1复制

0    3    2    
3    -1   1    
2    1    4    

说明/提示 数据规模与约定

对于全部的测试点，保证 1 leq x leq n leq 4001≤x≤n≤400，1 leq y leq m leq 4001≤y≤m≤400。

思路：就是一个求最短路径的问题，马走日所以它的扩展方向有八个 ，和走迷宫找最短路径的本质是一样的，每次循环，深度加一。

先初始化一个二维数组，所有元素为-1，起点（x，y）为0，然后开始bfs搜索，每进入一层，深度加一，该深度即步数，这一层的扩展点都是这个步数，一直到队列里没有元素了，整个二维数组就处理完毕，安装要求输出即可。

代码如下（注意点已经注释）

#include
#include
int n,m;
int mp[410][410];//棋盘
int book[410][410];//标记是否走过
//学到了新招就是自定义check函数检查有没有越界
//而且以越界条件先判断好像可以节省时间
//(因为只要一个条件不满足就是越界了)
//就不需要一个一个判断不越界的条件是否满足
int check(int x,int y)
{
    if(x<1||x>n||y<1||y>m)//注意噢x>n和y 
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: https://outofmemory.cn/zaji/5702722.html