P1443 马的遍历

题目描述

有一个 的棋盘，在某个点 上有一个马，要求你计算出马到达棋盘上任意一个点最少要走几步。

输入格式

输入只有一行四个整数，分别为 。

输出格式

一个 的矩阵，代表马到达某个点最少要走几步（不能到达则输出 ）。

输入输出样例 #1

输入 #1

3 3 1 1

输出 #1

0 3 2    
3 -1 1    
2 1 4

说明/提示

数据规模与约定

对于全部的测试点，保证 ，。

2022 年 8 月之后，本题去除了对输出保留场宽的要求。为了与之兼容，本题的输出以空格或者合理的场宽分割每个整数都将判作正确。

解题思路

这是一道标准的求一点到任意一点的最短路径问题，使用BFS进行解题，比较特殊的就是马的移动规则并不是直接的移位，而是“走日”。

有(1,2),(1,-2),(-1,2),(-1,-2),(2,1),(2,-1),(-2,1),(-2,-1)八种可能。

cpp代码如下：

#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
#include<deque>
#include<cmath>
#include<unordered_map>
using namespace std;

int readint(){
	char ch=getchar();
	int x=0;
	while(ch<'0' || ch>'9') ch=getchar();
	while(ch>='0' && ch<='9'){
		x=(x<<3)+(x<<1)+(ch^48);
		ch=getchar();
	}
	return x;
}
int dist[405][405];
int n,m,x,y;
int dx[8]={1,-1,1,-1,2,-2,2,-2},dy[8]={2,2,-2,-2,1,1,-1,-1};
void f(){
    queue<pair<int,int>> q;
    q.push({x,y});
    dist[x][y]=0;

    while(q.size()){
        auto cur=q.front();
        q.pop();
        for(int i=0;i<8;i++){
            int xn=cur.first+dx[i],yn=cur.second+dy[i];
            if(xn>=1&&xn<=n && yn>=1&&yn<=m && dist[xn][yn]==-1){
                dist[xn][yn]=dist[cur.first][cur.second]+1;
                q.push({xn,yn});
            }
        }
    }
}
int main(){
	n=readint();m=readint();x=readint();y=readint();
    memset(dist,-1,sizeof(dist));
    f();
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++) printf("%d ",dist[i][j]);
        printf("\n");
    } 
	return 0;
}