洛谷 P1443 马的遍历 BFS解

题目链接： 题目描述：

解题思路：

利用BFS求最短的思想，第一次到达的一定是最短的。首先将马的起点坐标入队列，然后定义一个数组记录到达这个位置的步数。

AC代码

#include <bits/stdc++.h>
using namespace std;
struct node{
          
   
    int x,y;
};
int vis[405][405]={
          
   0};
int cnt[405][405]={
          
   0};
int fx[8][2]={
          
   {
          
   2,1},{
          
   -2,1},{
          
   2,-1},{
          
   -2,-1},{
          
   -1,2},{
          
   1,2},{
          
   -1,-2},{
          
   1,-2}};
queue<node>q;
int main()
{
          
   
    int n,m,ex,ey;
    cin>>n>>m>>ex>>ey;
    vis[ex][ey]=1;
    q.push({
          
   ex,ey});
    while(q.size()){
          
   
        node p;
        p=q.front();
        q.pop();
        int x1=0,y1=0;
        for(int i=0;i<8;i++){
          
   
            x1=p.x+fx[i][0];
            y1=p.y+fx[i][1];
            //cout<<x1<<" "<<y1<<endl;
            if(x1<=n&&x1>0&&y1>0&&y1<=m&&vis[x1][y1]==0){
          
   
                q.push({
          
   x1,y1});
                cnt[x1][y1]=cnt[p.x][p.y]+1;
                vis[x1][y1]=1;
            }
        }
    }
    for(int i=1;i<=n;i++){
          
   
        for(int j=1;j<=m;j++){
          
   
            if(cnt[i][j])
                cout<<cnt[i][j]<<" ";
            else if(i==ex&&j==ey){
          
   
                cout<<cnt[i][j]<<" ";
            }
            else{
          
   
                    cout<<-1<<" ";
            }
        }
        cout<<endl;
    }
    return 0;
}