洛谷P1443 马的遍历——广搜

落日映苍穹つ 2023-09-26 18:19 92阅读 0赞

> ### 题目描述 ###
> 
> 有一个n×m 的棋盘，在某个点 (x, y) 上有一个马，要求你计算出马到达棋盘上任意一个点最少要走几步。
> 
> ### 输入格式 ###
> 
> 输入只有一行四个整数，分别为 n, m, x, y。
> 
> ### 输出格式 ###
> 
> 一个n×m 的矩阵，代表马到达某个点最少要走几步（不能到达则输出 −1）。
> 
> ### 输入输出样例 ###
> 
> **输入** 
> 
>     3 3 1 1
> 
> **输出** 
> 
>     0    3    2    
>     3    -1   1    
>     2    1    4
> 
> ### 说明/提示 ###
> 
> #### 数据规模与约定 ####
> 
> 对于全部的测试点，保证1≤x≤n≤400，1≤y≤m≤400。

#include<iostream>
    #include<iomanip>
    #include<cstdio>
    #include<queue>
    #include<cstring>
    using namespace std;
    
    int n, m, sx, sy;
    int mp[410][410];
    int xx[] = { 2,2, 1, 1,-1,-1,-2,-2 };
    int yy[] = { 1,-1,2,-2, 2,-2,1,-1 };
    struct node
    {
    	int x, y, s;
    };
    int main()
    {
    	cin >> n >> m >> sx >> sy;
    	memset(mp, -1, sizeof(mp));
    	queue<node>q;
    	node t;
    	t.x = sx; t.y = sy; t.s = 0;
    	q.push(node{ sx,sy,0 });
    	mp[sx][sy] = 0;
    	while (!q.empty())
    	{
    		for (int i = 0; i < 8; i++)
    		{
    			int dx = xx[i] + q.front().x;
    			int dy = yy[i] + q.front().y;
    			if (dx >= 1 && dx <= n && dy >= 1 && dy <= m && mp[dx][dy] == -1)
    			{
    				q.push(node { dx, dy, q.front().s + 1 });
    				mp[dx][dy] = q.front().s + 1;
    			}
    		}
    		q.pop();
    	}
    	for (int i = 1; i <= n; i++)
    	{
    		for (int j = 1; j <= m; j++)
    		{
    			printf("-5%d", mp[i][j]);
    		}
    		cout << endl;
    	}
    	return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，92人围观）

还没有评论，来说两句吧...

相关阅读

相关洛谷P1443 马的遍历——广搜

> 题目描述 > > 有一个n×m 的棋盘，在某个点 (x, y) 上有一个马，要求你计算出马到达棋盘上任意一个点最少要走几步。 > > 输入格式 > > 输入只

落日映苍穹つ/ 2023年09月26日 18:19/ 0 赞/ 93 阅读

相关 Java实现洛谷 P3916 图的遍历（反向DFS+记忆化搜索）

P3916 图的遍历 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9

小鱼儿/ 2023年07月22日 06:58/ 0 赞/ 3 阅读

相关 //众神云集、群魔乱舞、以一抵百、砥砺前行//P1443 马的遍历

题目描述题目描述有一个n\m的棋盘(1<n,m<=400)，在某个点上有一个马,要求你计算出马到达棋盘上任意一个点最少要走几步输入格式一行四个数据，棋盘

女爷i/ 2023年02月13日 11:54/ 0 赞/ 13 阅读

相关洛谷P1229 遍历问题

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

ゝ一世哀愁。/ 2023年01月17日 14:50/ 0 赞/ 204 阅读

相关 P1443 马的遍历（bfs）

注意左对齐，宽五格的输出，为此wa了两次 include <bits/stdc++.h> using namespace std; define in

短命女/ 2022年08月30日 15:58/ 0 赞/ 138 阅读

相关洛谷p1164

> P1164 小A点菜 > > 题目描述 > > uim口袋里有剩M元（M<=10000）。 > > 餐馆虽低端，但是菜品种类不少，有N种（N<=100），第i

亦凉/ 2022年06月09日 01:53/ 0 赞/ 321 阅读

相关洛谷 P3382

题目：[点击打开链接][Link 1] 题意：如题，给出一个N次函数，保证在范围\[l,r\]内存在一点x，使得\[l,x\]上单调增，\[x,r\]上单调减。试求出x

绝地灬酷狼/ 2022年05月14日 00:19/ 0 赞/ 316 阅读

相关洛谷P1002题解

include<iostream> using namespace std; long long a[30][30]={0},n,m,my,m

我会带着你远行/ 2022年03月19日 04:16/ 0 赞/ 349 阅读

相关洛谷 P4961

目录题目思路 Code 题目 [戳][Link 1] 为了小埋A了这道题。思路读入原来的矩阵，将不是雷的格子更新为数字（数字就是

左手的ㄟ右手/ 2021年10月26日 20:28/ 0 赞/ 439 阅读

相关洛谷P1443 马的遍历(bfs)

[https://www.luogu.org/problem/P1443][https_www.luogu.org_problem_P1443] 思路：马走日字格，它可以走十

谁借莪１个温暖的怀抱￠/ 2021年10月18日 15:44/ 0 赞/ 355 阅读