洛谷P1443 马的遍历——标准广度优先搜索

Solution：

这是一道标准的广度优先搜索题目。我们知道，马在棋盘上是按“日”行走的，也就是有八个方向，我们沿着这八个方向广度优先搜索就可以了。
代码如下：

#include<iostream>
#include<queue>
#include<stdio.h>
#define MAX 500
using namespace std;

int mp[MAX][MAX];//棋盘
int steps[MAX][MAX];//步数数组
int visit[MAX][MAX];//访问数组
int dir[][2]={{1,2},{1,-2},{2,-1},{2,1},{-1,-2},{-1,2},{-2,-1},{-2,1}};
                    //八个方向
int n,m;//n为行数，m为列数

struct xy{
  int x;
  int y;
}node,top;//坐标

void bfs(int x,int y,int step){
  steps[x][y]=step;//开始的点的步数为0
  visit[x][y]=1;//访问开始的点
  queue<xy> q;//队列
  node.x=x;
  node.y=y;
  q.push(node);//将开始的点入队列
  while(!q.empty()){
    top=q.front();
    q.pop();//取出首节点
    for(int i=0;i<8;i++){
        int xx=top.x+dir[i][0];
        int yy=top.y+dir[i][1];
        if(xx<1||xx>n||yy<1||yy>m){//若越界，就继续往下一个方向搜索
            continue;
        }
        if(visit[xx][yy]==0){//若没有访问过，就访问该节点
            node.x=xx;
            node.y=yy;
            q.push(node);//进队列
            visit[xx][yy]=1;
            steps[xx][yy]=steps[top.x][top.y]+1;//步数加1
        }
    }
  }
}

int main(){
  int sx,sy;
  cin>>n>>m>>sx>>sy;
  for(int i=0;i<MAX;i++){//初始化visit和steps数组
    for(int j=0;j<MAX;j++){
        visit[i][j]=0;
        steps[i][j]=-1;
    }
  }
  bfs(sx,sy,0);//bfs
  for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++){
        printf("%-5d",steps[i][j]);//左对齐并占5个字符
    }
    cout<<endl;
  }
  return 0;
}