首页 > 代码库 > P1443 马的遍历

P1443 马的遍历

2024-09-22 02:45:20   213人阅读

题目描述

有一个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<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cmath> 5 #include<queue> 6 using namespace std; 7 const int MAXN=501; 8 int map[MAXN][MAXN]; 9 int n,m,bgx,bgy;10 int xx[9]={-2,-1,+1,+2,+2,+1,-1,-2};11 int yy[9]={-1,-2,-2,-1,+1,+2,+2,+1};12 struct node13 {14     int x,y,step;15 }cur,nxt;16 void bfs()17 {18     cur.x=bgx;cur.y=bgy;cur.step=0;19     queue<node>q;20     q.push(cur);21     while(q.size()!=0)22     {23         node p=q.front();24         q.pop();25         for(int i=0;i<8;i++)26         {27             node nxt;28             nxt.x=p.x+xx[i];29             nxt.y=p.y+yy[i];30             nxt.step=p.step+1;31             if(nxt.x>=1&&nxt.x<=n&&nxt.y>=1&&nxt.y<=m&&map[nxt.x][nxt.y]==-1)32             {33                 map[nxt.x][nxt.y]=nxt.step;34                 q.push(nxt);35             }36         }37     }38 }39 int main()40 {41     scanf("%d%d%d%d",&n,&m,&bgx,&bgy);42     for(int i=1;i<=n;i++)43         for(int j=1;j<=m;j++)44             map[i][j]=-1;45     map[bgx][bgy]=0;46     bfs();47     for(int i=1;i<=n;i++)48     {49         for(int j=1;j<=m;j++)50         {51             printf("%-5d",map[i][j]);52         }53         printf("\n");54     }55     return 0;56 }

 

P1443 马的遍历


联系
我们