题解 P1443 【马的遍历】
Talanton_Cerydra · · 题解
bfs模板题目
bfs（广度优先搜索）需要一个队列来实现，算法就是在队列不为空的情况下，访问每一个点，访问后将与该点连接的所有点加入队列尾部，再将该点从队首退出。
struct node
{
int x,y,step;
}st;
queue<node>zjl;同时要建两个表示方向的数组，本题可以这么建：
int dx[8]={2,2,1,1,-1,-1,-2,-2},dy[8]={1,-1,2,-2,2,-2,1,-1};用2、1、-1、-2是因为马走日字，同一个下标的dx和dy相互对应，表示每一种走法
这题就很适用bfs，dfs根本没有用
下面让我们用代码来实现：
#include <bits/stdc++.h>//古老的万能头
using namespace std;//加了这个才能使用queue
int mp[402][402];//记录棋盘
int dx[8]={2,2,1,1,-1,-1,-2,-2},dy[8]={1,-1,2,-2,2,-2,1,-1};//前面已讲过
int n,m;
struct node
{
int x,y,step;
}st;
queue<node>zjl;//我有个好友姓名拼音首字母是zjl，所以这里引用一下（嘻嘻）
void bfs() //大头来了
{
zjl.push(st); //将起始坐标入队
mp[st.x][st.y]=0;//记录原点步数为0，显然
while(!zjl.empty())//只要队列不为空就一直循环
{
node t=zjl.front(); //临时变量t
zjl.pop();//队首已经存在t里了，可以出队
for(int i=0;i<8;i++)//走每种情况
{
int xx=t.x+dx[i];//走后的x坐标
int yy=t.y+dy[i];//走后的y坐标
if(xx<1||yy<1||xx>n||yy>m)//边界
{
continue;
}
if(mp[xx][yy]!=-1) //已访问
{
continue;
}
mp[xx][yy]=t.step+1;//步数加一
zjl.push((node){xx,yy,t.step+1});//将新能遍历的格子入队
}
}
}
int main()//主函数
{
memset(mp,-1,sizeof(mp));//先全初始化为-1与题目呼应
scanf("%d%d%d%d",&n,&m,&st.x,&st.y);//读入
bfs();//执行bfs函数
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
//双重循环输出
printf("%-5d",mp[i][j]);//注意输出的格式
}
printf("\n");//记得换行
}
return 0;
}