洛谷 - 1443:马的遍历

xiaoxiao2021-03-01  14

马的遍历

来源:洛谷

标签:

参考资料:

相似题目:

题目

有一个n*m的棋盘(1 < n,m <= 400),在某个点上有一个马,要求你计算出马到达棋盘上任意一个点的最小步数(马走“日”字)。

输入

一行四个数据,分别代表棋盘的大小和马的坐标。

输出

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

输入样例

3 3 1 1

输出样例

0 3 2 3 -1 1 2 1 4

解题思路

马走“日”字。采用BFS解决该问题。

参考代码

#include<stdio.h> #include<string.h> #include<queue> using namespace std; const int maxn=400+5; int arr[maxn][maxn],vis[maxn][maxn]; int tx[8]={-2,-2,2,2,-1,-1,1,1}, ty[8]={-1,1,-1,1,-2,2,-2,2}; int n,m; int posx,posy; queue<int> dotx,doty; void bfs(int x,int y) { dotx.push(x); doty.push(y); arr[x][y]=0; vis[x][y]=1; while(!dotx.empty()) { int x=dotx.front(); int y=doty.front(); dotx.pop(); doty.pop(); for(int i=0;i<8;i++) { int nx=x+tx[i],ny=y+ty[i]; if(nx>=0 && nx<n && ny>=0 && ny<m && vis[nx][ny]==0) { vis[nx][ny]=1; arr[nx][ny]=arr[x][y]+1; dotx.push(nx); doty.push(ny); } } } } int main() { scanf("%d%d%d%d",&n,&m,&posx,&posy); for (int i=0;i<n;i++) for (int j=0;j<m;j++) arr[i][j]=-1; posx-=1; posy-=1; bfs(posx,posy); for(int i=0;i<n;i++) { for(int j=0;j<m;j++) printf("%-5d",arr[i][j]); printf("\n"); } return 0; }
转载请注明原文地址: https://www.6miu.com/read-3350001.html

最新回复(0)