P1443 马的遍历——题解

解题思路

棋盘可视为一个无权图，每个格子与马一步能够到达的最多八个格子相连。从起点进行 BFS，第一次到达某格子时所用层数就是最短步数。距离数组初始为 $-1$，同时承担“是否访问过”的作用。

复杂度分析

共有 $nm$ 个状态，每个状态检查 8 个方向，时间复杂度 $O(nm)$，空间复杂度 $O(nm)$。

C++17 参考代码

#include <bits/stdc++.h>
using namespace std;
int d[405][405];
int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n,m,sx,sy; cin>>n>>m>>sx>>sy;
    for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) d[i][j]=-1;
    int dx[8]={1,1,2,2,-1,-1,-2,-2};
    int dy[8]={2,-2,1,-1,2,-2,1,-1};
    queue<pair<int,int>> q;
    d[sx][sy]=0; q.push({sx,sy});
    while(!q.empty()){
        int x=q.front().first,y=q.front().second; q.pop();
        for(int k=0;k<8;k++){
            int nx=x+dx[k],ny=y+dy[k];
            if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&d[nx][ny]==-1){
                d[nx][ny]=d[x][y]+1; q.push({nx,ny});
            }
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++) cout<<d[i][j]<<(j==m?'\n':' ');
    }
    return 0;
}

#include <bits/stdc++.h> using namespace std; int d[405][405]; int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int n,m,sx,sy; cin>>n>>m>>sx>>sy; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) d[i][j]=-1; int dx[8]={1,1,2,2,-1,-1,-2,-2}; int dy[8]={2,-2,1,-1,2,-2,1,-1}; queue<pair<int,int>> q; d[sx][sy]=0; q.push({sx,sy}); while(!q.empty()){ int x=q.front().first,y=q.front().second; q.pop(); for(int k=0;k<8;k++){ int nx=x+dx[k],ny=y+dy[k]; if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&d[nx][ny]-1){ d[nx][ny]=d[x][y]+1; q.push({nx,ny}); } } } for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++) cout<<d[i][j]<<(jm?'\n':' '); } return 0; }