首页 > 代码库 > 洛谷——P1443 马的遍历
洛谷——P1443 马的遍历
https://www.luogu.org/problem/show?pid=1443#sub
题目描述
有一个n*m的棋盘(1<n,m<=400)，在某个点上有一个马,要求你计算出马到达棋盘上任意一个点最少要走几步
输入输出格式
输入格式：
一行四个数据，棋盘的大小和马的坐标
输出格式：
一个n*m的矩阵，代表马到达某个点最少要走几步（左对齐，宽5格，不能到达则输出-1）
输入输出样例
输入样例#1：
3 3 1 1
输出样例#1：
0 3 2 3 -1 1 2 1 4
1 #include <algorithm> 2 #include <cstring> 3 #include <cstdio> 4 #include <queue> 5 6 using namespace std; 7 8 const int N(405); 9 int n,m,x,y;10 11 struct Node12 {13 int x,y;14 }node;15 int cnt[N][N],vis[N][N];16 int fx[8]={1,1,2,2,-1,-1,-2,-2};17 int fy[8]={2,-2,1,-1,2,-2,1,-1};18 queue<Node>que;19 void BFS(Node s)20 {21 que.push(s); cnt[s.x][s.y]=0;22 for(;!que.empty();)23 {24 Node a,fro=que.front();que.pop();25 for(int i=0;i<8;i++)26 {27 int xx=fro.x+fx[i],yy=fro.y+fy[i];28 if(cnt[xx][yy]!=-1||xx<1||yy<1||xx>n||yy>m) continue;29 cnt[xx][yy]=cnt[fro.x][fro.y]+1;30 a.x=xx,a.y=yy; que.push(a);31 }32 }33 }34 35 int main()36 {37 scanf("%d%d%d%d",&n,&m,&node.x,&node.y);38 memset(cnt,-1,sizeof(cnt));39 BFS(node);40 for(int i=1;i<=n;i++)41 {42 for(int j=1;j<=m;j++)43 printf("%-5d",cnt[i][j]);44 printf("\n");45 }46 return 0;47 }
洛谷——P1443 马的遍历
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。