洛谷笔记 - P1443 马的遍历

发表于 更新于 本文字数： 460 阅读时长 ≈ 2 分钟

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

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

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

题目描述

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

输入格式

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

输出格式

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

样例 #1

样例输入 #1

1
3 3 1 1

样例输出 #1

1
2
3
0    3    2    
3    -1   1    
2    1    4

提示

数据规模与约定

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

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
// 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;
}

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

前途未卜。