题解 P1443 【马的遍历】

· · 题解

这道题蒟蒻是用宽搜的，不知道别的大佬是怎样。

主要坑点：1.走的步数会达10000以上；

         2.输出空格时要注意，需用printf("%-5d", a[i][j])。

上蒟蒻臃肿的代码

#include<bits/stdc++.h>//蒟蒻不知到memset的头文件，如果有人知道，请私信给我，蒟蒻十分感谢。
using namespace std;
struct sb
{
    int x,y;
}que[100001];//记步数（坑点1）
const int dx[8]={-2,-1,1,2,2,1,-1,-2},dy[8]={-1,-2,-2,-1,1,2,2,1};//8个方向
int n,m;
bool cheak(int x,int y)
{
    if(x>0&&x<=n&&y>0&&y<=m)return 1;
    return 0;
}//作用是判断是否越界。（蒟蒻懒得写在主程序里。）
int main()
{
    int sx,sy,i,a[401][401];
    memset(a,-1,sizeof(a));//初始化为每个点都无法到达
    cin>>n>>m>>sx>>sy;
    a[sx][sy]=0;
    que[1].x=sx;
    que[1].y=sy;
    int head=0,tail=1;
    while(head<tail)
    {
        head++;
        for(i=0;i<8;i++)
        {
            if(a[que[head].x+dx[i]][que[head].y+dy[i]]==-1&&cheak(que[head].x+dx[i],que[head].y+dy[i]))
            {
                tail++;
                que[tail].x=que[head].x+dx[i];
                que[tail].y=que[head].y+dy[i];
                a[que[tail].x][que[tail].y]=a[que[head].x][que[head].y]+1;
            }
        }
    }
    for(i=1;i<n;i++)
    {
        for(int j=1;j<=m;j++)
        printf("%-5d",a[i][j]);//坑点2（大坑点）蒟蒻在这卡了2次
        cout<<endl;
    }//怕换行算错，故意这样分两段
    for(int j=1;j<=m;j++)
    printf("%-5d", a[i][j]);
    return 0;//完美结束
}

希望伟大的管理员给通过