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

· · 题解

洛谷P12270

看了一圈，总算找到一个能写题解的搜索题了……

题意：

给一个边长为 n 的棋盘，并给出马与象的位置和移动规则，求走几步之后一方能吃掉另一方，如果双方累死也吃不到，就输出 -1 。

思路：

用两次bfs广搜：

  1. 第一次搜索马的可能位置（搜象也行）并将跳到该点 (i,j) 的步数记录在二维数组 mp1[i][j] 里。

  2. 第二次搜索象的可能位置（同理），将步数记录在另一个二维数组 mp2[i][j] 里。

  3. 最后枚举每个点，求该点马跳的步数与象走的步数之和，取最小值输出即可。

也可以直接在第二次搜索中直接搜出答案。

雷：

棋盘内 (0,x) 和 (y,0) 是可以走到的！注意边界判断

最后上AC代码：

#include<bits/stdc++.h>
using namespace std;
int mp1[59][59],mp2[59][59],f,r;//初始化棋盘
int x,x2,y,y2,n;
bool flag[59][59];
pair<int,int>q[5009];//bfs队列
int dx1[8]={-2,-2,-1,-1,2,2,1,1};//马的移动方向（日字）
int dy1[8]={1,-1,2,-2,1,-1,2,-2};//马的移动方向
int dx2[4]={2,2,-2,-2};//象的移动方向（田字）
int dy2[4]={2,-2,2,-2};//象的移动方向
void bfsh()//搜马
{
    f=r=0;
    memset(mp1,0x7f,sizeof(mp1));//初始化清空
    memset(flag,false,sizeof(flag));
    mp1[x][y]=0;//初始化步数
    flag[x][y]=true;
    q[++r]={x,y};
    while(f<r)
    {
        f++;
        int qx=q[f].first,qy=q[f].second;
        for(int i=0;i<8;i++)
        {
            int xx=qx+dx1[i],yy=qy+dy1[i];向外走一步
            if(xx<0||xx>n||yy<0||yy>n)continue;//判断越界
            if(mp1[xx][yy]==0x7f7f7f7f)//判断是否走过
            {
                mp1[xx][yy]=mp1[qx][qy]+1;//记录答案
                flag[xx][yy]=true;//标记
                q[++r]={xx,yy};//入队
            }
        }
    }
}
void bfse()//搜象
{
    f=r=0;
    memset(mp2,0x7f,sizeof(mp2));//初始化清空
    memset(flag,false,sizeof(flag));
    mp2[x2][y2]=0;//初始化步数
    flag[x2][y2]=true;
    q[++r]={x2,y2};
    while(f<r)
    {
        f++;
        int qx=q[f].first,qy=q[f].second;
        for(int i=0;i<4;i++)
        {
            int xx=qx+dx2[i],yy=qy+dy2[i];
            if(xx<0||xx>n||yy<0||yy>n)continue;//判断越界
            if(mp2[xx][yy]==0x7f7f7f7f)//判断是否走过
            {
                mp2[xx][yy]=mp2[qx][qy]+1;//记录答案
                flag[xx][yy]=true;
                q[++r]={xx,yy};
            }
        }
    }
}
int main()
{
    cin>>n>>x>>y>>x2>>y2;
    if(x==x2&&y==y2)//没什么用的特判
    {
        cout<<0;
        return 0;
    }
    bfsh();//搜马
    bfse();//搜象
    int ans=INT_MAX;//初始化答案
    for(int i=0;i<=n;i++)
    {
        for(int j=0;j<=n;j++)
        {
            if(mp1[i][j]!=0x7f7f7f7f&&mp2[i][j]!=0x7f7f7f7f)
                ans=min(ans,mp1[i][j]+mp2[i][j]);//更新答案
        }
    }
    cout<<(ans==INT_MAX?-1:ans);//如果答案为最大值则输出-1
}