马的遍历
发布时间
阅读量：
阅读量
题目描述
在一个n*m的棋盘（1＜n,m≤400）中，某个位置放置了一匹马，需要计算该马到达棋盘上任意一点所需的最少步数
输入格式
输入包含四个数值，依次为棋盘的行数、列数以及马的初始位置坐标
输出格式
输出一个n*m的矩阵，其中每个元素表示马到达对应位置所需的最少步数（左对齐，宽度为5个字符，若无法到达则显示-1）
输入输出样例
输入
3 3 1 1
输出
0 3 2
3 -1 1
2 1 4
思路：采用广度优先搜索的方式遍历所有可能的八个移动方向，检查是否超出棋盘范围，并对已访问的位置进行标记。当所有可能路径均被搜索完成后，仍未被标记的位置即表示无法到达。
#include <bits/stdc++.h>
using namespace std;
int n,m,startx,starty;
int a[401][401] ,book[401][401];//输出数组a和标记数组book
typedef struct //状态结构体
{ int x;
int y;
int step;//当前步数
}Satus;
int BFS(int sx,int sy )
{ int i,next[8][2]={{-1,2},{1,2},{全部评论 (0)
还没有任何评论哟~