独有病眼花,春风吹不落。 (二维坐标压缩成一个点,并查集)

本题链接:登录—专业IT笔试面试备考平台_牛客网

题目:

样例:

输入
3 8
1 1 D
1 1 R
1 2 D
2 1 D
2 2 R
3 1 R
3 2 R
2 3 D
输出
8

思路:

        根据题意,要求连接线段后,操作多少次,连接的线段闭合,如果操作完都没有闭合,说明平局输出“draw”。

        在这里,我们可以将线段当作拥有两个点,当我们所画的线段两端的点是头和尾的时候,说明我们画闭合了。所以根据寻找当前点的根结点的时候就是头结点。我们很容易联想到并查集。

        这里有个难题就是如何将二维坐标化成一个点的形式存在。我们可以通过映射的方式,由于坐标的 x,y是唯一坐标,所以我们可以结合 x 和 y的结合唯一特点性,转化为一个点映射在我们范围之外即可。

二维坐标化为一个点函数:

inline int getPost(int x,int y)
{return x*n + y;
}

随后就是模板并查集的合并查询操作即可。

代码详解如下:

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#define endl '\n'
#define x first
#define y second
#define int long long
#define YES puts("YES")
#define NO puts("NO")
#define umap unordered_map
#define All(x) x.begin(),x.end()
#pragma GCC optimize(3,"Ofast","inline")
#define IOS std::ios::sync_with_stdio(false),cin.tie(0), cout.tie(0)
using namespace std;
const int N = 2e7 + 10;
inline void solve();signed main()
{
//	freopen("a.txt", "r", stdin);IOS;int _t = 1;// cin >> _t;while (_t--){solve();}return 0;
}
int n,m;
int f[N];// 二维坐标转化一维点
inline int getPost(int x,int y)
{return x*n + y;
}
inline void Init()
{for(int i = 1;i <= n * n;++i) f[i] = i;
}
inline int Finds(int x)
{int t = x;while(f[x] != x) x = f[x];f[t] = x;return x;
}
inline void solve()
{cin >> n >> m;Init();	// 并查集初始化操作for(int step = 1;step <= m;++step){int x,y;char op;cin >> x >> y >> op;--x,--y;	// 小优化,省一省空间int b,a = getPost(x,y);	// 二维坐标转化一维点if(op == 'D') b = getPost(x + 1,y);else b = getPost(x,y + 1);a = Finds(a),b = Finds(b);	// 查找线段两端的根节点if(a == b)	// 如果两端的根节点一致,说明出现了闭区间{cout << step << endl;return ;}f[a] = b;	// 合并区间}cout << "draw" << endl;
}

最后提交:

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://xiahunao.cn/news/3017058.html

如若内容造成侵权/违法违规/事实不符,请联系瞎胡闹网进行投诉反馈,一经查实,立即删除!

相关文章

Windows安全加固-账号与口令管理

在当今日益增长的网络安全威胁中&#xff0c;Windows系统的安全加固显得尤为重要。其中&#xff0c;账号与口令管理作为系统安全的第一道防线&#xff0c;其重要性不言而喻。本文将深入探讨Windows安全加固中的账号与口令管理策略&#xff0c;以确保系统的安全性和稳定性。 账…

2009-2022年上市公司华证ESG评级评分数据(含细分项)

2009-2022年上市公司华证ESG评级评分数据&#xff08;含细分项&#xff09; 1、时间&#xff1a;2009-2022年 2、来源&#xff1a;华证ESG 3、指标&#xff1a;证券代码、证券简称、综合评级、年度、综合得分、E评级、E得分、S评级、S得分、G评级、G得分 4、范围&#xff1…

Linux实现Flappy bird项目

目录 1、项目介绍 2、功能总结 3、前期准备 3.1 Ncurses库 3.2 信号机制 3.2.1 设置信号响应方式 3.2.2 设置定时器 4、代码实现 4.1 头文件引用及变量、函数定义 4.2 主函数 4.3 curses初始化 4.4 设置定时器 4.5 定时器响应函数 4.6 小鸟控制相关函数 4…

Go语言fmt包深度探索:格式化输入输出的利器

&#x1f525; 个人主页&#xff1a;空白诗 文章目录 &#x1f3ad; 引言一、基础输出函数fmt.Print与fmt.Println&#x1f4cc; fmt.Print&#xff1a;纯粹输出&#xff0c;不带换行&#x1f4cc; fmt.Println&#xff1a;输出后自动添加换行符 二、格式化输出fmt.Printf&…

【C语言】用数组和函数实现扫雷游戏

用数组和函数实现扫雷游戏 游戏界面&#xff1a; 代码如下&#xff1a; game.h #pragma once #include <stdio.h> #include <stdlib.h> #include <time.h> #define EASY_COUNT 10 #define ROW 9 #define COL 9 #define ROWS ROW2 #define COLS COL2 //初始…

Error Code: 1449. The user specified as a definer (‘admin‘@‘%‘) does not exist

前言 在进行MySQL数据库迁移或存储过程部署时&#xff0c;您可能会遇到错误 [Err] 1449 - The user specified as a definer (admin%) does not exist。这篇文章将为您提供一个详细的解决方案&#xff0c;帮助您顺利解决这一问题。 错误背景 此错误通常发生在尝试执行一个存…

国货美妆进入新纪元之际,毛戈平打好“高端牌”了吗?

当前&#xff0c;国内美妆市场的格局已发生较大变化。 一边是国际品牌的“退场”&#xff0c;据统计&#xff0c;2023年退出中国市场的海外美妆品牌有20多个&#xff1b;一边是国内美妆品牌正在迎来自己的时代。 根据魔镜洞察数据&#xff0c;2024年一季度&#xff0c;国货彩…

【Linux】Linux线程

一、Linux线程的概念 1.什么是线程 1.一个进程的一个执行线路叫做线程&#xff0c;线程的一个进程内部的控制序列。 2.一个进程至少有一个执行线程 3.线程在进程内部&#xff0c;本质是在进程地址空间内运行 4.操作系统将进程虚拟地址空间的资源分配给每个执行流&#xff0…

GoLang实战——微服务网关

1. 网关 1.1. 网关应该具备的基本功能 支持多种协议代理&#xff1a;tcp/http/websocket/grpc支持多种负载均衡策略&#xff1a;轮询/权重轮询/hash一致性支持下游服务发现&#xff1a;主动探测/自动服务发现支持横向扩容&#xff1a;加机器就能解决高并发 1.2. 借助网关处理…

ldap对接jenkins

ldap结构 配置 - jenkins进入到 系统管理–>全局安全配置 - 安全域 选择ldap - 配置ldap服务器地址&#xff0c;和配置ldap顶层唯一标识名 配置用户搜索路径 - 配置管理员DN和密码 测试认证是否OK

MCU做死循环时,到底应该用for(;;) 还是wihile(1)

MCU做死循环时 for while stm32中老工程师用forfor while背景for版本while版本正方观点&#xff1a;哪有好的编译器&#xff1a;反方观点&#xff1a;这种代码过时了工程师实地测试&#xff1a;和编译器和优化有关 建议还是用for参考 stm32中老工程师用for /* Start scheduler …

数据库系统理论——绪论

文章目录 前言一、数据库四个基本概念1、数据2、数据库3、数据库管理系统&#xff08;DBMS&#xff09;4、数据库系统&#xff08;DBS&#xff09; 二、数据模型1、概念数据模型2、逻辑数据模型3、物理数据模型 三、三级模式1、图片解析2、二级映像 前言 最近很长时间没更新学…

windows 双网卡同时接入内外网

在公司使用wifi接入使用桌面云&#xff0c;但是公司wifi不能上外网&#xff0c;查资料不方便&#xff0c;通过手机同时接入外网。 同一台电脑设置同时连接内外网&#xff08;wifi或共享的网络&#xff09;_win7电脑同时使用手机和usb网卡使用wifi-CSDN博客 route print查看当前…

开启智能新纪元:揭秘现代化仓储物流园区的数字孪生魅力

在数字化浪潮的推动下&#xff0c;物流行业正迎来前所未有的变革&#xff0c;现代化仓储物流园区数字孪生系统正以其独特的魅力引领着物流行业迈向更加智能、高效的新时代。 图源&#xff1a;山海鲸可视化 一、数字孪生&#xff1a;物流行业的“虚拟镜像” 数字孪生技术作为工…

5.合并两个有序数组

文章目录 题目简介题目解答解法一 &#xff1a;合并后排序解法二&#xff1a;双指针排序 题目链接 大家好&#xff0c;我是晓星航。今天为大家带来的是 合并两个有序数组 相关的讲解&#xff01;&#x1f600; 题目简介 题目解答 解法一 &#xff1a;合并后排序 假设我们要合…

科研学习|可视化——ggplot2版本的网络可视化

ggplot2是R语言中一个非常流行的数据可视化包&#xff0c;它也可以用于网络可视化。以下是三个基于ggplot2并专门用于网络可视化的R包&#xff1a; ggnet2: 这个包的使用方法与传统的plot函数相似&#xff0c;易于使用。更多信息可在其官方页面查看&#xff1a;ggnet2 geomnet…

【Linux网络】PXE批量网络装机

目录 一、系统装机 1.1 三种引导方式 1.2 系统安装过程 1.3 四大重要文件 二、PXE 2.1 PXE实现原理 2.2 PXE手动搭建过程 2.3 kickstart配合pxe完成批量自动安装 一、系统装机 1.1 三种引导方式 硬盘光驱(U盘)网络启动 1.2 系统安装过程 加载boot loader加载启动安…

《安富莱嵌入式周报》第336期:开源计算器,交流欧姆表,高性能开源BLDC控制器,Matlab2024a,操作系统漏洞排名,微软开源MS-DOS V4.0

周报汇总地址&#xff1a;嵌入式周报 - uCOS & uCGUI & emWin & embOS & TouchGFX & ThreadX - 硬汉嵌入式论坛 - Powered by Discuz! 本周更新一期视频教程&#xff1a; BSP视频教程第30期&#xff1a;UDS ISO14229统一诊断服务CAN总线专题&#xff0c;常…

学习和分析各种数据结构所要掌握的一个重要知识——CPU的缓存利用率(命中率)

什么是CPU缓存利用率&#xff08;命中率&#xff09;&#xff0c;我们首先要把内存搞清楚。 硬盘是什么&#xff0c;内存是什么&#xff0c;高速缓存是什么&#xff0c;寄存器又是什么&#xff1f; 我们要储存数据就要运用到上面的东西。首先里面的硬盘是可以无电存储的&#…

记一次DNS故障导致用户无法充值的问题(上)

背景&#xff1a; 刚刚过去了五一劳动节&#xff0c;回来后一上班接到客服运营团队反馈的节日期间的问题&#xff0c;反馈有部分用户无法充值。拿到的反馈资料有&#xff1a; 无法充值操作视频、问题时间、手机机型、手机网络情况。 1、从视频中看到用户点击支付后没有任何反…