首页 > 代码库 > 洛谷——P1443 马的遍历

洛谷——P1443 马的遍历

2024-10-19 21:18:02   213人阅读

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 马的遍历


联系
我们