第 2 届河北省大学生程序设计竞赛(河北省赛)-Problem L. 跑图-题解

2024-04-11 11:08

本文主要是介绍第 2 届河北省大学生程序设计竞赛(河北省赛)-Problem L. 跑图-题解,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

传送门

Problem A. Mex Query
Problem B. Nim Game
Problem C. icebound 的账单
Problem G. 520
Problem H. 神殿
Problem J. icebound 的商店
Problem K. Bitmap
       哈希讲解
       二维哈希讲解
Problem L. 跑图





Problem L. 跑图

Time Limit: 1000ms
Memory Limit: 65536KB

Description

跑图是RPG游戏中很烦躁的事情。玩家需要跑到距离他最近的传送点的位置。现在给你一张 N × M N \times M N×M的方格图,每个方格中数值 0 0 0表示为平地,数值 1 1 1表示为传送点,你的任务是输出一张 N × M N \times M N×M的矩阵, M a t r i x x y Matrix_{xy} Matrixxy表示从 ( x , y ) (x,y) (x,y)到距离它最近的传送点的距离。 这里的距离是曼哈顿距离, ( x 1 , y 1 ) → ( x 2 , y 2 ) (x_1,y_1) \rightarrow(x_2,y_2) (x1,y1)(x2,y2)的距离为 ∣ x 1 − x 2 ∣ + ∣ y 1 − y 2 ∣ |x_1-x_2|+|y_1-y_2| x1x2+y1y2

Input

第一行,有两个数 n , m n,m n,m。接下来 n n n行,每行 m m m个数。

数据保证至少有一个传送点。

1 ≤ n ≤ 500 1 \leq n \leq 500 1n500 1 ≤ m ≤ 500 1 \leq m \leq 500 1m500

Output

n n n行,每行 m m m个数,表示某个点到离它最近的传送点的距离。

Sample Input

2 3
0 0 0
1 0 1

Sample Output

1 2 1
0 1 0

题目大意

给你个地图,每个点初始值为 0 0 0 1 1 1。让你计算出每个点到任意一个 1 1 1的最近的距离。


解题思路

这是一道广搜题。简单说一下:
我们以所有初始值为 1 1 1的点为起点,入队,它们所能到达且未到达过的点是它的值加一。

队列中的初始的点是所有出发点,凡是它们能一步到达(且未达到过)的地方,答案都是1。
然后这个能到达的地方就会被放到队尾,直到所有的出发点全部出队,就轮到答案是1的点了。
答案是1的点能够一步到达的且未到达过的点,答案都是2。之后它们也入队。
等所有答案都是1的点都出队后,该由答案为2的点为起点 ⋯ \cdots
⋯ \cdots
直到队列为空,输出答案即可。

AC代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
bool sf[510][510]={0};//是否出现过。没出现过用false,出现过用ture。
int a[510][510]={0};//最终要输出的地图的结果
int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};//每个点有4个方向:上下左右。dir是direction的缩写。{1,0}代表x+1,y+0
int main()
{int n,m;cin>>n>>m;queue<pair<int,int> >q;//每个节点的pair<int,int>的两个数分别代表x和yfor(int i=0;i<n;i++)//输入部分{for(int j=0;j<m;j++){int t;scanf("%d",&t);if(t)//如果t初始值是1{sf[i][j]=1;//这一点答案就是0,已经走过q.push(pair<int,int>(i,j));//入队}}}while(q.size())//队列不空时{pair<int,int>thisPair=q.front();//取出队首的元素q.pop();for(int i=0;i<4;i++)//4个方向{int tx=thisPair.first+dir[i][0];//to x:要到的x的坐标int ty=thisPair.second+dir[i][1];//t0 y:要到的y的坐标if(tx>=0&&tx<n&&ty>=0&&ty<m&&!sf[tx][ty])//如果tx在[0,n)并且ty在[0,m)并且这一点还没有处理过{sf[tx][ty]=1;//现在这一点处理过了a[tx][ty]=a[thisPair.first][thisPair.second]+1;//这一点的值是上一点的值+1q.push(pair<int,int>(tx,ty));//入队}}}for(int i=0;i<n;i++)//打印{for(int j=0;j<m;j++){printf("%d ",a[i][j]);//输出}puts("");//换行}return 0;
}

原创不易,转载请附上原文链接哦~
Tisfy:https://letmefly.blog.csdn.net/article/details/116537689

这篇关于第 2 届河北省大学生程序设计竞赛(河北省赛)-Problem L. 跑图-题解的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/893905

相关文章

csu 1446 Problem J Modified LCS (扩展欧几里得算法的简单应用)

这是一道扩展欧几里得算法的简单应用题,这题是在湖南多校训练赛中队友ac的一道题,在比赛之后请教了队友,然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意:把题意转变下就变成了:求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点:求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个

uva 10025 The ? 1 ? 2 ? ... ? n = k problem(数学)

题意是    ?  1  ?  2  ?  ...  ?  n = k 式子中给k,? 处可以填 + 也可以填 - ,问最小满足条件的n。 e.g k = 12  - 1 + 2 + 3 + 4 + 5 + 6 - 7 = 12 with n = 7。 先给证明,令 S(n) = 1 + 2 + 3 + 4 + 5 + .... + n 暴搜n,搜出当 S(n) >=

C++ | Leetcode C++题解之第393题UTF-8编码验证

题目: 题解: class Solution {public:static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num &

C语言 | Leetcode C语言题解之第393题UTF-8编码验证

题目: 题解: static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num & MASK1) == 0) {return

每日一题|牛客竞赛|四舍五入|字符串+贪心+模拟

每日一题|四舍五入 四舍五入 心有猛虎,细嗅蔷薇。你好朋友,这里是锅巴的C\C++学习笔记,常言道,不积跬步无以至千里,希望有朝一日我们积累的滴水可以击穿顽石。 四舍五入 题目: 牛牛发明了一种新的四舍五入应用于整数,对个位四舍五入,规则如下 12345->12350 12399->12400 输入描述: 输入一个整数n(0<=n<=109 ) 输出描述: 输出一个整数

C - Word Ladder题解

C - Word Ladder 题解 解题思路: 先输入两个字符串S 和t 然后在S和T中寻找有多少个字符不同的个数(也就是需要变换多少次) 开始替换时: tips: 字符串下标以0开始 我们定义两个变量a和b,用于记录当前遍历到的字符 首先是判断:如果这时a已经==b了,那么就跳过,不用管; 如果a大于b的话:那么我们就让s中的第i项替换成b,接着就直接输出S就行了。 这样

C语言程序设计(数据类型、运算符与表达式)

一、C的数据类型 C语言提供的数据类型: 二、常量和变量 2.1常量和符号常量 在程序运行过程中,其值不能被改变的量称为常量。 常量区分为不同的类型: 程序中用#define(预处理器指令)命令行定义变量将代表常量,用一个标识符代表一个常量,称为符合常量。 2.2变量 变量代表内存中具有特定属性的一个存储单元,用来存放数据,在程序运行期间,这些值是可以 改变的。 变

【秋招笔试】9.07米哈游秋招改编题-三语言题解

🍭 大家好这里是 春秋招笔试突围,一起备战大厂笔试 💻 ACM金牌团队🏅️ | 多次AK大厂笔试 | 大厂实习经历 ✨ 本系列打算持续跟新 春秋招笔试题 👏 感谢大家的订阅➕ 和 喜欢💗 和 手里的小花花🌸 ✨ 笔试合集传送们 -> 🧷春秋招笔试合集 🍒 本专栏已收集 100+ 套笔试题,笔试真题 会在第一时间跟新 🍄 题面描述等均已改编,如果和你笔试题看到的题面描述

C语言程序设计(选择结构程序设计)

一、关系运算符和关系表达式 1.1关系运算符及其优先次序 ①<(小于) ②<=(小于或等于) ③>(大于) ④>=(大于或等于 ) ⑤==(等于) ⑥!=(不等于) 说明: 前4个优先级相同,后2个优先级相同,关系运算符的优先级低于算术运算符,关系运算符的优先级高于赋值运算符 1.2关系表达式 用关系运算符将两个表达式(可以是算术表达式或关系表达式,逻辑表达式,赋值表达式,字符

LeetCode 第414场周赛个人题解

目录 Q1. 将日期转换为二进制表示 原题链接 思路分析 AC代码 Q2. 范围内整数的最大得分 原题链接 思路分析 AC代码 Q3. 到达数组末尾的最大得分 原题链接 思路分析 AC代码 Q4. 吃掉所有兵需要的最多移动次数 原题链接 思路分析 AC代码 Q1. 将日期转换为二进制表示 原题链接 Q1. 将日期转换为二进制表示 思路分析