题解：P12270 [蓝桥杯 2024 国 Python B] 马与象

LoyalSoldier · 2025-04-23 20:51:33 · 题解

本题算法：BFS（广度优先搜索）。
难度建议：橙。
这题说实话，很简单，我十五分钟就写出来了，这是模版题。
我们来说一下本题的思路：

• 首先，我们要知道的是广度优先搜索的原理：在原点进行扩散，对于每一个 a_{i,j}，扩散了之后也要从 (i,j) 这个位置开始扩散。当 (x,y) 被第一次扩散到时，那么它离原点的距离就是你扩散的次数。
• 然后，我们来想，既然题目要求最少步数，那么我们可以写两个函数，一个扩散马，一个扩散象。注意：我们的下标是 0 到 n，只要 (i,j) 合法才进行扩散，否则不行。
• 最后，我们需要计算步数。遍历这个棋盘的所有点。在此之前，我们可以定义两个数组 mway 和 xway，是二维数组。用来记录步数。(i,j) 的最少步数就是 mway_{i,j}+xway_{i,j}，最后取最小值即可。
• 注意：如果没有最小值，我们需要输出 -1。

接下来我们来讲一下代码实现细节：

• 方向数组的找法。我举个例子，我们找象的方向数组。从左上到右上，先依次数坐标 x 偏移了多少，再数 y 偏移了多少，把偏移量记录到方向数组即可。马的也就同理了。
• 我们一开始的时候要把所以的步数设为最大值，因为如果 (i,j) 走不到，那么我们的步数是 0 时最小步数就是 0，而这个点走不到，与题目不符。所以我们可以写个循环，把 mway_{i,j},xway_{i,j} 设为极大值。
• 我们可以用一个队列维护搜索时扩散的顺序，每扩散一个，就把这个点弹出队列。每找到一个可以扩散的点，就把它给装进队列。

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl "\n";
const int maxn=1005;
struct node{
    int x,y;
    int step;
};
int n,mx,my,xx,xy;
//m开头的遍历是关于马的数组，x开头的数组和象有关。
int mway[maxn][maxn],xway[maxn][maxn];//记录每个位置的步数
bool mvis[maxn][maxn],xvis[maxn][maxn];
int mdx[]={-2,-1,1,2,2,1,-1,-2},mdy[]={-1,-2,-2,-1,1,2,2,1};//方向数组
int xdx[]={-2,2,2,-2},xdy[]={-2,-2,2,2};
bool mcheck(int x,int y){
    if(x<0||x>n||y<0||y>n){//越界了
        return true;
    }
    if(mvis[x][y]){//走过了
        return true;
    }
    return false;
}
bool xcheck(int x,int y){
    if(x<0||x>n||y<0||y>n){
        return true;
    }
    if(xvis[x][y]){
        return true;
    }
    return false;
}
void mbfs(){
    queue<node>q;
    q.push({mx,my,0});//把原点入队
    while(!q.empty()){
        node t=q.front();
        q.pop();
        for(int i=0;i<8;i++){
      //计算下一步走到的位置
            int nx=mdx[i]+t.x;
            int ny=mdy[i]+t.y;
            if(mcheck(nx,ny)){//不合法
                continue;
            }
            mvis[nx][ny]=true;
            q.push({nx,ny,t.step+1});
            mway[nx][ny]=t.step+1;//计算步数，是在上一个点走过来的，所以要加一
        }
    }
}
void xbfs(){
    queue<node>q;
    q.push({xx,xy,0});
    while(!q.empty()){
        node t=q.front();
        q.pop();
        for(int i=0;i<4;i++){
            int nx=xdx[i]+t.x;
            int ny=xdy[i]+t.y;
            if(xcheck(nx,ny)){
                continue;
            }
            xvis[nx][ny]=true;
            q.push({nx,ny,t.step+1});
            xway[nx][ny]=t.step+1;
        }
    }
}
signed main(){
    cin>>n>>mx>>my>>xx>>xy;
    for(int i=0;i<=n;i++){
        for(int j=0;j<=n;j++){
            mway[i][j]=INT_MAX;
            xway[i][j]=INT_MAX;
        }
    }
    mvis[mx][my]=true;
    xvis[xx][xy]=true;
    mway[mx][my]=0;
    xway[xx][xy]=0;
    mbfs();
    xbfs();
    int mini=INT_MAX;
    for(int i=0;i<=n;i++){
        for(int j=0;j<=n;j++){
            mini=min(mway[i][j]+xway[i][j],mini);//计算步数总和
        }
    }
    if(mini==INT_MAX){//特判，如果答案不存在，输出-1
        cout<<-1<<endl;
        return 0;
    }
    cout<<mini<<endl;
    return 0;
}