本文介绍: 有一个n×m棋盘,在某个点xy上有一个马,要求你计算出马到达棋盘任意一个点最少要走几步。

马的遍历

题目描述

一个

n

×

m

n times m

n×m棋盘,在某个点

(

x

,

y

)

(x, y)

(x,y) 上有一个马,要求你计算出马到达棋盘上任意一个点最少要走几步。

输入格式

输入只有一行四个整数,分别为

n

,

m

,

x

,

y

n, m, x, y

n,m,x,y

输出格式

一个

n

×

m

n times m

n×m矩阵代表马到达某个点最少要走几步(不能到达则输出

1

-1

1)。

样例 #1

样例输入 #1

3 3 1 1

样例输出 #1

0    3    2    
3    -1   1    
2    1    4

提示

数据规模与约定

对于全部的测试点,保证

1

x

n

400

1 leq x leq n leq 400

1xn400

1

y

m

400

1 leq y leq m leq 400

1ym400

AC代码

#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
const int N = 510;
int ans[N][N],n,m,x,y;
const int dx[8] = { -1,-2,-2,-1,1,2,2,1 };
const int dy[8] = { 2,1,-1,-2,2,1,-1,-2 };
typedef pair<int, int&gt;PII;//开一个可以两个int的变量用于坐标(x,y)
queue<PII&gt; q;

void bfs()
{
	//队列非空
	while (!q.empty())
	{
		auto now = q.front();//记录当前队列元素
		q.pop();//将队列的首元素弹出
		int d = ans[now.first][now.second];
		for (int i = 0; i < 8; i++)
		{
			int ax = now.first + dx[i];
			int ay = now.second + dy[i];
			//如果跨过边界了或者当前位置访问过了,就直接continue不管
			if (ax<1 || ax&gt;n || ay<1 || ay&gt;m || ans[ax][ay] != -1)
				continue;
			ans[ax][ay] = d + 1;//在上一次距离加上1
			q.push({ ax,ay });//继续入队列
		}
	}
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			printf("%-5d", ans[i][j]);
		}
		puts("");
	}
}

int main(void)
{
	cin >> n >> m >> x >> y;
	memset(ans, -1,sizeof ans);//没有访问标记为-1
	ans[x][y] = 0;//从[x,y]走的,当前格子步数就是0
	q.push({ x,y });//将[x,y]坐标加入到队列当中
	bfs();
	return 0;
}

原文地址:https://blog.csdn.net/2301_79516932/article/details/134793942

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任

如若转载,请注明出处:http://www.7code.cn/show_42162.html

如若内容造成侵权/违法违规/事实不符,请联系代码007邮箱suwngjj01@126.com进行投诉反馈,一经查实,立即删除

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注