初探广度优先搜索bfs~队列~马的遍历（题目来源：洛谷P1443~马的遍历）
题目描述
有一个n*m的棋盘(1<n,m<=400)，在某个点上有一个马,要求你计算出马到达棋盘上任意一个点最少要走几步。
输入格式
一行四个数据，棋盘的大小和马的坐标。
输出格式
一个n*m的矩阵，代表马到达某个点最少要走几步（左对齐，宽5格，不能到达则输出-1）。
输入输出样例
输入：
3 3 1 1
输出：
0 3 2
3 -1 1
2 1 4
代码实现：c++
思想：广搜，队列
具体代码：（在借鉴洛谷题解后才成功解题，注释与完整代码为本人原创）
#include
#include //使用队列queue
#include //使用memset初始化
#include
#include //格式化输入输出，方便，用iomanip也可
using namespace std;
const int maxn=405;//棋盘大小上限
int n,m;
struct xy{
int x,y;
}node,Top;//定义结构体，用于队列
int a[maxn][maxn];
bool b[maxn][maxn];//判断马是否已经走过这一步
//判断的原因：如果马已经走过这一步，那么已经
//走过的步数一定是最少的步数，这样才符合题意。
int dx[]={1,-1,2,-2};
int dy[]={1,-1,2,-2};//方向数组，用于循环
void solve(int x,int y,int cnt)
{
memset(a,-1,sizeof(a));/*初始化为-1
假设一开始每一个地方都走不到，这样在最后
就不必特判走不到的位置。*/
memset(b,true,sizeof(b));
/*b数组用于记录是否走过，true代表走过
false代表没走过，一开始默认全部走过。*/
queue Q;//构建队列
node.x=x,node.y=y;
/*node为一个结构变量，用于存储x和y坐标，其
存在的意义类似于temp~暂时存放，不断变化
（工具人）*/
a[x][y]=cnt;//主函数中传入的坐标为(0，0)
//当然（0，0）也就是起点坐标，根据题意
//该点设置为0.
b[x][y]=false;//该点设置为已到达
Q.push(node);//将起点压入，用于广搜
while(!Q.empty()){//循环条件为队列不为空
Top=Q.front();/*将每次循环开始时
，将队列起点元素赋值给Top*/
Q.pop();//弹出
for(int i=0;i<4;i++){
for(int j=0;j<4;j++){
if(abs(dx[i])!=abs(dy[j])){
//abs()为绝对值函数。
int Newx=Top.x+dx[i],Newy=Top.y+dy[j];
//Newx，Newy为马在该点可到达的位置的坐标。
if(Newx<1||Newyn||Newy>m) continue;//判断是否越界
if(b[Newx][Newy]){
//如果这一步之前没到达过，进入if语句
node.x=Newx,node.y=Newy;
//node赋新值，准备将这一点压入队列。
Q.push(node);
b[Newx][Newy]=false;
//该点设置为已到达。
a[Newx][Newy]=a[Top.x][Top.y]+1;
//如果该点能到达，那么走到这一点
//需要的步数为走到上一个点所需步数+1
}
}
}
}
}
}
int main()/*主函数作用是输入与输出，解决问题的
核心是solve函数*/
{
cin>>n>>m;
int x,y;
cin>>x>>y;
solve(x,y,0);
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
printf("%-5d",a[i][j]);
}
cout<<endl;
}
return 0;
}
队列
队列这一概念本人早有耳闻（本人目前对于编程为入门状态，从刚开始接触至今尚未满一年@@），但将其应用于做题中是最近的事。队列是只允许在一段进行插入操作，而在另一端进行删除操作的线性表队列是一种先进先出的线性表，简称FIFO（First In First Out）。允许插入的一端成为队尾，允许删除的一端称为对头。（摘自大话数据结构，书中具体讲述了如何用C语言与结构构建队列，但此处直接用c++自带的队列容器更方便）
除普通队列之外，优先队列（priority_queue）在做题中（贪心greedy）也有应用，之后更新的博客将会提及。
鄙人才疏学浅，代码简陋，讲解过程中难免有不严谨之处，敬请看客谅解！
fatfairyyy
原创文章 2获赞 2访问量 41
关注
私信
展开阅读全文
作者：fatfairyyy
