2733: 【搜索】【广度优先】 马遍历棋盘

本文主要是介绍2733: 【搜索】【广度优先】 马遍历棋盘，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述

有一个n*m的棋盘(1<n,m<=400)，在某个点上有一个马,要求你计算出马到达棋盘上任意一个点最少要走几步

输入

一行四个数据，棋盘的大小和马的坐标

输出

一个n*m的矩阵，代表马到达某个点最少要走几步（左对齐，宽5格，不能到达则输出-1）

样例输入

4 4 1 1

样例输出

0    3    2    5
3    4    1    2
2    1    4    3
5    2    3    2

Code:

#include<bits/stdc++.h>
using namespace std;
struct node{int x,y;
}temp,front;
int dx[4]={1,-1,2,-2};
int dy[4]={1,-1,2,-2};
int a[401][401];
bool vis[401][401];
int n,m;
void bfs(int x,int y,int step){a[x][y]=step;vis[x][y]=true;queue<node>Q;temp.x=x;temp.y=y;Q.push(temp);while(!Q.empty()){front=Q.front();Q.pop();for(int i=0;i<4;i++){for(int j=0;j<4;j++){if(abs(dx[i])!=abs(dy[j])){int nx=front.x+dx[i];int ny=front.y+dy[j];if(nx<1||nx>n||ny<1||ny>m){continue;}if(!vis[nx][ny]){temp.x=nx;temp.y=ny;Q.push(temp);vis[nx][ny]=true;a[nx][ny]=a[front.x][front.y]+1;}}}}}
}
int main(){memset(a,-1,sizeof(a));int x,y;cin>>n>>m>>x>>y;bfs(x,y,0);for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){printf("%-5d",a[i][j]);}cout<<endl;}return 0;
}

这篇关于2733: 【搜索】【广度优先】 马遍历棋盘的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---