格子游戏——并查集
Alice和Bob玩了一个古老的游戏:首先画一个 n×n 的点阵(下图 n=3 )。
接着,他们两个轮流在相邻的点之间画上红边和蓝边:

直到围成一个封闭的圈(面积不必为 1)为止,“封圈”的那个人就是赢家。因为棋盘实在是太大了,他们的游戏实在是太长了!他们甚至在游戏中都不知道谁赢得了游戏。
于是请你写一个程序,帮助他们计算他们是否结束了游戏?
输入格式
输入数据第一行为两个整数 n 和 m。n表示点阵的大小,m 表示一共画了 m 条线。
以后 m 行,每行首先有两个数字 (x,y),代表了画线的起点坐标,接着用空格隔开一个字符,假如字符是 D,则是向下连一条边,如果是 R 就是向右连一条边。
输入数据不会有重复的边且保证正确。
输出格式
输出一行:在第几步的时候结束。
假如 m 步之后也没有结束,则输出一行“draw”。
数据范围
1≤n≤200,1≤m≤24000
输入样例:
3 5
1 1 D
1 1 R
1 2 D
2 1 R
2 2 D
输出样例:
4
解析:
当给出(a,b)和(c,d) 时,若在连接这两个点之前,两个点已经连通,此时再添加这条边,就构成了一个“ 封闭的圈 ”。
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int> PII;
const int N=2e6+10;
map <PII,int> s;
int p[N];
int find(int x)
{if (x!=p[x]) p[x]=find(p[x]);return p[x];
}
signed main()
{int n,m;cin>>n>>m;int cnt=0;for (int i=1;i<=n;i++)for (int j=1;j<=n;j++)s[{i,j}]=++cnt;for (int i=1;i<=cnt;i++) p[i]=i;int a,b,x,y;char c;for (int i=1;i<=m;i++){cin>>a>>b>>c;if (c=='D') x=a+1,y=b;else x=a,y=b+1;int l=s[{a,b}],r=s[{x,y}];if (find(l)!=find(r)) p[find(l)]=find(r);else{cout<<i;return 0;}}cout<<"draw";return 0;
}
相关文章:
格子游戏——并查集
Alice和Bob玩了一个古老的游戏:首先画一个 nn 的点阵(下图 n3 )。 接着,他们两个轮流在相邻的点之间画上红边和蓝边: 直到围成一个封闭的圈(面积不必为 1)为止,“封圈”的那个人就是…...
2023最新Python重点知识万字汇总
这是一份来自于 SegmentFault 上的开发者 二十一 总结的 Python 重点。由于总结了太多的东西,所以篇幅有点长,这也是作者"缝缝补补"总结了好久的东西。 **Py2 VS Py3** * print成为了函数,python2是关键字* 不再有unicode对象…...
【STM32】学习笔记(TIM定时器)-江科大
TIM(Timer)定时器 定时器可以对输入的时钟进行计数,并在计数值达到设定值时触发中断 16位计数器、预分频器、自动重装寄存器的时基单元,在72MHz计数时钟下可以实现最大59.65s的定时 不仅具备基本的定时中断功能,而且…...
Parallel Context Windows for Large Language Models
本文是LLM系列文章,针对《Parallel Context Windows for Large Language Models》的翻译。 大语言模型并行上下文窗口 摘要1 引言2 并行上下文窗口3 上下文学习的PCW4 PCW用于QA5 相关工作6 结论和未来工作不足 摘要 当应用于处理长文本时,大型语言模型…...
怎么消除人声保留背景音乐?试试这几种简单方法
消除人声保留背景音乐可以用于许多不同的目的。例如,可以在视频制作中使用,以确保观众能够听到清晰的对话,而不会被其他噪音干扰。此外,它也可以用于音乐制作中,以便更好地混合和控制音频元素。教大家几种简单的提取方…...
积分游戏小程序模板源码
积分游戏小程序模板源码是一款可以帮助用户快速开发小程序的工具,此模板源码包含五个静态页面,分别是首页、任务列表、大转盘、猜拳等五个页面,非常适合进行积分游戏等相关开发。 此模板源码的前端部分非常简单易用,用户可以根据…...
IDEA启动两个Tomcat服务的方式 使用nginx进行反向代理 JMeter测试分布式情况下synchronized锁失效
目录 引出IDEA启动Tomcat两个端口的方式1.编辑配置2.添加新的端口-Dserver.port80833.service里面管理4.启动后进行测试 使用nginx进行反向代理反向代理多个端口运行日志查看启动关闭重启 分布式情况下synchronized失效synchronized锁代码启动tomcat两个端口nginx反向代理JMete…...
Shell 脚本入门
目录 一、Shell是什么 1.1 我们为什么要学习Shell和使用Shell? 1.2 Shell的分类有哪些? 二、Shell脚本入门知识 2.1 Shell文件命名规范 2.2 Shell解析器 2.3 用Shell 编写hello World 三、Shell的四种变量类型 3.1 系统预定义变量 3.2 自定义变…...
管理类联考——逻辑——形式逻辑——汇总篇——知识点突破——性质模态
性质&模态 角度一 角度二 矛盾关系 【对象】(1)所有、有的不;(2)所有不、有的;(3)某个、某个不。 【典例】①所有偶像都是靠颜值的。 ②有的偶像不是靠颜值的。 试分析: (1)如果①为真,试判断②的真假。 (2)如果①为假,试判断②的真假。 (3)①和②是否可…...
无涯教程-Android - ToggleButton函数
ToggleButton将已选中/未选中状态显示为按钮。它基本上是一个带有指示灯的开/关按钮。 Toggle Button ToggleButton属性 以下是与ToggleButton控件相关的重要属性。您可以查看Android官方文档以获取属性的完整列表以及可以在运行时更改这些属性的相关方法。 Sr.No.Attribute…...
unity VS无法进行断点调试
有时候我们的VS无法进行断点调试,报错如下: 原因是:开启了多个项目,vs无法找到调式项目 解决:点击菜单栏--调试----附加unity调试程序 会弹出一个框,然后选择你要调试的项目 即可...
Pandas由入门到精通-组合与合并数据
采集的数据存储后通常会分为多个文件或数据库,如何将这些文件按需拼接,或按键进行连接十分重要。这节将介绍数据索引的复杂操作如分层索引,stack,unstack,seet_index,reset_index等帮助重构数据,数据的拼接如merge,join,concat,combine_first等帮助连接数据,以及数据透视表…...
Unexpected mutation of “xxxx“ prop
原因 是因为子级修改了父级的数据,所以eslint执行的时候报了这个错 修复方式 1 如果是弹窗等组件,可以根据功能进行修改,比如我这块用的 element ui 的 dialog,便可以改成这样 使用 model-value 代替 修复方式 2 新建子组件…...
七、基础篇总结
...
前端面试基础面试题——2
1.什么是json? json可以存在哪几种数据类型?在什么时候用? 2.什么是作用域? 3.http和https分别是什么?区别是什么? 4.介绍一下js的节流与防抖? 5.什么是cookie?cookie的优缺点。 6.js的三种排序方法࿰…...
docker 搭建rknn转换环境
文章目录 下载rknn搭建docker 环境进入镜像并挂载运行代码 下载rknn https://github.com/rockchip-linux/rknn-toolkit2 搭建docker 环境 进入到docker 的文件目录下 docker build -t run:v3 . -f Dockerfile_ubuntu_18_04_for_cp36 进入镜像并挂载 docker run -it -v /ho…...
机器学习:争取被遗忘的权利
随着越来越多的人意识到他们通过他们经常访问的无数应用程序和网站共享了多少个人信息,数据保护和隐私一直在不断讨论。看到您与朋友谈论的产品或您在 Google 上搜索的音乐会迅速作为广告出现在您的社交媒体提要中,这不再那么令人惊讶。这让很多人感到担…...
MATLAB实现AHP层次分析法——以情人节选取礼物为例
问题背景: 情人节来临之际,广大直男(女)同胞在给异性朋友选购礼物时会遇到难题——什么才是礼物好坏最重要的标准?基于层次分析法AHP进行计算,得出最高权重的指标,给出各位朋友选购礼物的一种思…...
flutter使用Chanel与原生通信
在Flutter中,Platform Channel允许Flutter与原生平台(如Android和iOS)之间进行双向通信,以便在Flutter应用程序和原生代码之间传递消息和调用功能。 以下是使用Platform Channel与原生通信的一般步骤: 1. 在Flutter端…...
Kubernetes技术--k8s核心技术Helm
1.引入 我们先回顾一下之前部署一个应用的过程,如部署nginx,实现效果如下所示: -1.编写deployment的yaml文件,然后运行。 -2.使用service中的NodePort对外暴漏端口 -3.为了弥补Nodeport的缺陷,使用ingress实现转发 这样一个应用就部署完了,这一种情况相对于如果你需要部…...
Flask RESTful 示例
目录 1. 环境准备2. 安装依赖3. 修改main.py4. 运行应用5. API使用示例获取所有任务获取单个任务创建新任务更新任务删除任务 中文乱码问题: 下面创建一个简单的Flask RESTful API示例。首先,我们需要创建环境,安装必要的依赖,然后…...
边缘计算医疗风险自查APP开发方案
核心目标:在便携设备(智能手表/家用检测仪)部署轻量化疾病预测模型,实现低延迟、隐私安全的实时健康风险评估。 一、技术架构设计 #mermaid-svg-iuNaeeLK2YoFKfao {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg…...
从深圳崛起的“机器之眼”:赴港乐动机器人的万亿赛道赶考路
进入2025年以来,尽管围绕人形机器人、具身智能等机器人赛道的质疑声不断,但全球市场热度依然高涨,入局者持续增加。 以国内市场为例,天眼查专业版数据显示,截至5月底,我国现存在业、存续状态的机器人相关企…...
ServerTrust 并非唯一
NSURLAuthenticationMethodServerTrust 只是 authenticationMethod 的冰山一角 要理解 NSURLAuthenticationMethodServerTrust, 首先要明白它只是 authenticationMethod 的选项之一, 并非唯一 1 先厘清概念 点说明authenticationMethodURLAuthenticationChallenge.protectionS…...
Java 加密常用的各种算法及其选择
在数字化时代,数据安全至关重要,Java 作为广泛应用的编程语言,提供了丰富的加密算法来保障数据的保密性、完整性和真实性。了解这些常用加密算法及其适用场景,有助于开发者在不同的业务需求中做出正确的选择。 一、对称加密算法…...
Typeerror: cannot read properties of undefined (reading ‘XXX‘)
最近需要在离线机器上运行软件,所以得把软件用docker打包起来,大部分功能都没问题,出了一个奇怪的事情。同样的代码,在本机上用vscode可以运行起来,但是打包之后在docker里出现了问题。使用的是dialog组件,…...
IP如何挑?2025年海外专线IP如何购买?
你花了时间和预算买了IP,结果IP质量不佳,项目效率低下不说,还可能带来莫名的网络问题,是不是太闹心了?尤其是在面对海外专线IP时,到底怎么才能买到适合自己的呢?所以,挑IP绝对是个技…...
GruntJS-前端自动化任务运行器从入门到实战
Grunt 完全指南:从入门到实战 一、Grunt 是什么? Grunt是一个基于 Node.js 的前端自动化任务运行器,主要用于自动化执行项目开发中重复性高的任务,例如文件压缩、代码编译、语法检查、单元测试、文件合并等。通过配置简洁的任务…...
C++.OpenGL (20/64)混合(Blending)
混合(Blending) 透明效果核心原理 #mermaid-svg-SWG0UzVfJms7Sm3e {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-SWG0UzVfJms7Sm3e .error-icon{fill:#552222;}#mermaid-svg-SWG0UzVfJms7Sm3e .error-text{fill…...
Bean 作用域有哪些?如何答出技术深度?
导语: Spring 面试绕不开 Bean 的作用域问题,这是面试官考察候选人对 Spring 框架理解深度的常见方式。本文将围绕“Spring 中的 Bean 作用域”展开,结合典型面试题及实战场景,帮你厘清重点,打破模板式回答,…...
