洛谷P1443 马的遍历——广搜

落日映苍穹つ 2023-09-26 18:19 110阅读 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 条评论，110人围观）

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

相关阅读

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

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

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

相关洛谷P1162 填涂颜色——广搜

> 题目描述 > > 由数字 0 组成的方阵中，有一任意形状闭合圈，闭合圈由数字 1 构成，围圈时只走上下左右 4 个方向。现要求把闭合圈内的所有空间都填写成 22。例如

逃离我推掉我的手/ 2023年09月26日 18:19/ 0 赞/ 66 阅读

相关【洛谷 P1514】引水入城 I 广搜 + 区间覆盖

[https://www.luogu.org/problem/P1514][https_www.luogu.org_problem_P1514] NOIP 在一个遥远的国

约定不等于承诺〃/ 2023年06月03日 15:54/ 0 赞/ 8 阅读

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

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

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

相关洛谷P1229 遍历问题

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

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

相关 P1443 马的遍历（bfs）

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

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

相关洛谷p1164

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

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

相关洛谷 P3382

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

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

相关洛谷 P4961

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

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

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

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

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