洛谷笔记 - P1443 马的遍历

这道题是备考摸鱼的时候做的，应该能算广度优先搜索的模板？

很有用，也很绕，有点看不懂

好难啊我有点看不懂我也是六年级啊不过我有亲身体会,这种题目要自己做要不然还是会不懂的要不你去问问老师父母或同学

题目描述

有一个 $n \times m$ 的棋盘，在某个点 $(x, y)$ 上有一个马，要求你计算出马到达棋盘上任意一个点最少要走几步。

输入格式

输入只有一行四个整数，分别为 $n, m, x, y$。

输出格式

一个 $n \times m$ 的矩阵，代表马到达某个点最少要走几步（左对齐，宽 $5$ 格，不能到达则输出 $-1$）。

样例 #1

样例输入 #1

3 3 1 1

样例输出 #1

0    3    2    
3    -1   1    
2    1    4

提示

数据规模与约定

对于全部的测试点，保证 $1 \leq x \leq n \leq 400$，$1 \leq y \leq m \leq 400$。

代码

// Problem: P1443 马的遍历
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P1443
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<iostream>
#include<iomanip>
#include<deque>
using namespace std;
int main(){
    deque<int> x,y;
    int n,m,xx,yy,hy[8]={1,2,2,1,-1,-2,-2,-1},zy[8]={-2,-1,1,2,2,1,-1,-2};
    bool nn[401][401];
    int ans[401][401];
    cin>>n>>m>>yy>>xx;
    x.push_back(xx);
    y.push_back(yy);
    nn[yy][xx]=1;
    ans[yy][xx]=0;
    while(!x.empty()){
        for(int i=0;i<8;i++){
            if(x.front()+hy[i]>=1&&x.front()+hy[i]<=m&&y.front()+zy[i]>=1&&y.front()+zy[i]<=n&&nn[y.front()+zy[i]][x.front()+hy[i]]==0){
                nn[y.front()+zy[i]][x.front()+hy[i]]=1;
                ans[y.front()+zy[i]][x.front()+hy[i]]=ans[y.front()][x.front()]+1;
                x.push_back(x.front()+hy[i]);
                y.push_back(y.front()+zy[i]);
            }
        }
        x.pop_front();
        y.pop_front();
    }
    for(int i=1;i<=n;i++){
        for(int o=1;o<=m;o++){
            if(nn[i][o])
                cout<<left<<setw(5)<<ans[i][o];
            else cout<<left<<setw(5)<<"-1";
        }
        cout<<endl;
    }
    return 0;
}

有一说一，全国乙卷是真难。

前途未卜。