洛谷 /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{2,1}, //下右日     {2，-1}     {2，1}     {2，-1}     {1，2}     {-1，2}     {1，-2}     {-1,-2} };//左上日 struct queue//因为是bfs，要用到队列结构体 {     int x;     int y; } que[160001]*400 void bfs(int x,int y)//注意广度优先搜索 {     int head=0,tail=1;     int sum=0；///步数清零     ///初始点入队     que[1].x=x;     que[1].y=y;     //标记初始点     book[x][y]=1;     mp[x][y]=0;     while(head