题解 P1443 【马的遍历】

CXY07 · 2018-06-10 10:18:15 · 题解

一只蒟蒻的第一篇题解，一道裸的广搜，用 BFS 队列做的，只用了4ms。

其实就是把棋盘上的每一个点按照规则入队，第一次到达该点时的步数一定是最优步数（废话）

我觉得最需要注意的就是程序中 que 数组的大小，尝试开 20000 后在第九个点RE了，过了好久才发现问题 0.0

上代码：

#include<bits/stdc++.h>
using namespace std;
struct queue_
{
    int x,y;//一个结构体，x，y是队列该位置放的点的x，y值
} que[160010];//这里一定要注意数组大小，我在这里RE了两次！！
int head=0,tail=1,get[401][401],n,m,sx,sy;
int fx[16]={2,-2,2,-2,-1,1,-1,1},fy[16]={1,1,-1,-1,2,2,-2,-2};//方向
int main()
{
    cin>>n>>m>>sx>>sy;
    for(int i=1;i<=n;++i)
        for(int j=1;j<=m;++j)
            get[i][j]=-1;//初始化
    get[sx][sy]=0;//第一个点入队
    que[1].x=sx;
    que[1].y=sy;
    while(head<tail)
    {
        head++;//头指针加1
        int s=get[que[head].x][que[head].y]+1;//这个s是指扩展到新点时所需要的最少步数，就是上一个点的步数加1
        for(int i=0;i<8;++i)
        {
            int nx=que[head].x+fx[i],ny=que[head].y+fy[i];//扩展新点
            if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&get[nx][ny]==-1)//没有超出棋盘并且没有走过
            {
                tail++;
                que[tail].x=nx;
                que[tail].y=ny;//新点入队
                get[nx][ny]=s;//标记到达该点的最小步数
            }
        }
    }
    for(int i=1;i<=n;++i)
    {
        for(int j=1;j<=m;++j)
            printf("%-5d", get[i][j]);//输出，注意格式
        cout<<endl;
    }
    return 0; //华丽丽地结束
}

如果有错误或者有更好的办法，欢迎大佬们赐教 QWQ

蒟蒻的题解就这么结束啦，值得纪念

2019.8.1 UPD

考古

嗯......蒟蒻的第一篇题解，现在来看还是有很多地方说得不够清楚，所以现在 update 一下，并把之前一些有问题的地方改掉了。

首先，是数组大小的问题，请注意数据的范围，1<n,m<=400，也就是说，这个棋盘最大将是 400 × 400，而如果数据正好 n == 400 且 m == 400，则此时共有160000 (400^2)个点，又题目需要我们求出到达所有点的步数，也就是所有点都需要入队一次，那么需要 160000 (400^2) 的数组大小。

也就是说，如果数据更大一些，我的代码应该是过不了的 幸好数据水

还有一个，Julao 们说可以用 STL ，是的没错，的确可以用，并且这样在本题中还可以忽略爆数组的可能，超级便利。但是当时的我不知道怎么用 qwq ,现在补上

对于一些不知道 queue 和 pair 的童鞋，这边推荐您上网自行度娘的呢

这里的 pair 可以用结构体来代替，看个人喜好

还有一点，之前我在更新的时候，把 get 数组的判断放在了前面，这样有时候是会 RE 的

if(get[nx][ny]==-1&&nx>=1&&nx<=n&&ny>=1&&ny<=m)

应改为

if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&get[nx][ny]==-1)