格子游戏——并查集

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;
}

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

leetcode739. 每日温度 单调栈

自己思路&#xff1a; 想到用两个栈&#xff0c;一个维护元素、另一个维护下标。但是还是无法处理有重复元素的问题&#xff08;用哈希表来存储的时候&#xff09;。所以就看了答案的思路。 答案思路&#xff1a; 从前往后遍历&#xff0c;维护一个单调栈。栈存放数组的下标。…

css background实现四角边框

2023.8.27今天我学习了如何使用css制作一个四角边框&#xff0c;效果如下&#xff1a; .style{background: linear-gradient(#33cdfa, #33cdfa) left top,linear-gradient(#33cdfa, #33cdfa) left top,linear-gradient(#33cdfa, #33cdfa) right top,linear-gradient(#33cdfa, #…

【Debug】解决RecursionError: maximum recursion depth exceeded in comparison报错

&#x1f680;Debug专栏 目录 &#x1f680;Debug专栏 ❓❓问题&#xff1a; &#x1f527;&#x1f527;分析&#xff1a; &#x1f3af;&#x1f3af;解决方案&#xff1a; ❓❓问题&#xff1a; 循环中报错RecursionError: maximum recursion depth exceeded in compari…

electron globalShortcut 快捷键,在焦点移到其他软件上时,调用快捷键报错

用 electron 开发软件&#xff0c;在设置了 globalShortcut 快捷键后&#xff0c;在当前开发的软件上调用快捷键正常&#xff0c;但是当焦点不在当前软件时&#xff0c;在使用快捷键&#xff0c;好些时候会报错。大概率与系统快捷键产生冲突或者快键键控制的回调里获取的内容&a…

云计算 - 百度AIStudio使用小结

云计算 - 百度AIStudio使用小结 前言 本文以ffmpeg处理视频为例&#xff0c;小结一下AI Studio的使用体验及一些避坑技巧。 算力获得 免费的算力获得方式为&#xff1a;每日登录后运行一个项目&#xff08;只需要点击运行&#xff0c;不需要真正运行&#xff09;即可获得8小…

Python爬虫异常处理实践:处理被封禁和网站升级问题

在这篇文章中&#xff0c;我们将一起探讨Python爬虫异常处理实践&#xff0c;特别关注处理被封禁和网站升级问题。让我们一起来看看如何解决这些问题&#xff0c;提高我们爬虫程序的稳定性和可靠性。   首先&#xff0c;我们要了解为什么会遇到这些问题。网站封禁爬虫的原因主…

广州华锐互动:VR垃圾分类虚拟科普系统让学习过程更加丰富有趣

在我们的日常生活中&#xff0c;垃圾分类已成为一项重要的公民责任。然而&#xff0c;由于缺乏对垃圾分类的深入理解和相关知识&#xff0c;许多人在实践中往往感到困惑和挫败。为了解决这个问题&#xff0c;一种创新的解决方案应运而生&#xff1a;垃圾分类VR虚拟仿真教学系统…

【校招VIP】前端算法考察之排序

考点介绍&#xff1a; 不同的场景中&#xff0c;不同的排序算法执行效率不同。 稳定&#xff1a;冒泡、插入、归并 不稳定&#xff1a;选择、快速、堆排序、希尔排序 『前端算法考察之排序』相关题目及解析内容可点击文章末尾链接查看&#xff01; 一、考点题目 1、使用js实…

科大讯飞永久免费GPT入口来了!!!

讯飞GPT永久免费使用入口注册链接&#xff1a;讯飞星火认知大模型-AI大语言模型-星火大模型-科大讯飞。 登录讯飞账号后&#xff0c;点击进入体验。 进入体验页面后&#xff0c;选择景点推荐。 笔者让其写一篇关于讯飞GPT介绍的文案。 讯飞GPT是一款由讯飞公司推出的人工智能语…

【算法专题突破】双指针 - 盛最多水的容器(4)

目录 1. 题目解析 2. 算法原理 3. 代码编写 写在最后&#xff1a; 1. 题目解析 题目链接&#xff1a;11. 盛最多水的容器 - 力扣&#xff08;Leetcode&#xff09; 这道题目也不难理解&#xff0c; 两边的柱子的盛水量是根据短的那边的柱子决定的&#xff0c; 而盛水量…

MySQL项目迁移华为GaussDB PG模式指南

文章目录 0. 前言1. 数据库模式选择&#xff08;B/PG&#xff09;2.驱动选择2.1. 使用postgresql驱动2.1. 使用opengaussjdbc驱动 3. 其他考虑因素4. PG模式4.1 MySQL和OpenGauss不兼容的语法处理建议4.2 语法差异 6. 高斯数据库 PG模式JDBC 使用示例验证6. 参考资料 本章节主要…

配置uniapp调试环境

目录 uni-app介绍 uni-app开发工具HBuilderX 创建项目前提条件 uni-app项目结构 配置mumu模拟器 uni-app生命周期 1.应用生命周期 小程序规范 2.页面生命周期-小程序规范 3.组件生命周期 vue规范 uni-app登录按钮方法 uni-app发布安卓app uni-app介绍 uni-app 是一个…

JavaScript设计模式(二)——简单工厂模式、抽象工厂模式

个人简介 &#x1f440;个人主页&#xff1a; 前端杂货铺 &#x1f64b;‍♂️学习方向&#xff1a; 主攻前端方向&#xff0c;正逐渐往全干发展 &#x1f4c3;个人状态&#xff1a; 研发工程师&#xff0c;现效力于中国工业软件事业 &#x1f680;人生格言&#xff1a; 积跬步…

ASUS华硕天选4笔记本电脑FA507XV原厂Windows11系统22H2

天选四FA507X原装系统自带所有驱动、出厂主题壁纸LOGO、Office办公软件 华硕电脑管家、奥创控制中心等预装程序&#xff0c;恢复出厂状态W11 链接&#xff1a;https://pan.baidu.com/s/1SPoFW7wR5KawGu-yMckNzg?pwdayxd 提取码&#xff1a;ayxd

开源与可持续发展:环境友好的技术选择

&#x1f337;&#x1f341; 博主猫头虎 带您 Go to New World.✨&#x1f341; &#x1f984; 博客首页——猫头虎的博客&#x1f390; &#x1f433;《面试题大全专栏》 文章图文并茂&#x1f995;生动形象&#x1f996;简单易学&#xff01;欢迎大家来踩踩~&#x1f33a; &a…

【数据结构大全】你想要的都有,数组、链表、堆栈、二叉树、红黑树、B树、图......

目录 1.概述 2.线性结构 3.时间复杂度 4.查找算法 5.树 6.图 1.概述 博主之前写过一个完整的关于数据结构的系列文章&#xff0c;一共十三篇&#xff0c;内容包含&#xff0c;数组、链表、堆栈、队列、时间复杂度、顺序查找、二分查找、二叉树、二叉搜索树、平衡二叉树、…

电脑不安装软件,怎么将手机文件传输到电脑?

很多人都知道&#xff0c;AirDroid有网页版&#xff08;web.airdroid.com&#xff09;。 想要文件传输&#xff0c;却不想在电脑安装软件时&#xff0c;AirDroid的网页版其实也可以传输文件。 然而&#xff0c;要将文件从手机传输文件到网页端所在的电脑时&#xff0c;如果按…

JavaIO流

JavaIO流 一、概念二、File类三、File类的使用1、File文件/文件夹类的创建2、File类的获取操作3、File类判断操作 - boolean4、File类对文件/文件夹的增删改5、File类的获取子文件夹以及子文件的方法 四、Java中IO流多种维度的维度1、按照流向 - Java程序2、按照流的大小分类3、…

LInux之chrony服务器

目录 场景 重要性 LInux的两个时钟 硬件时钟 系统时钟 NTP协议 Chrony介绍 定义 组成 --- chronyd和chronyc 安装与配置 安装 Chrony配置文件分析 同步时间服务器 chronyc命令 chronyc sources输出分析 其它命令 查看时间服务器的状态 查看时间服务器是否在线 …

18-使用钩子函数判断用户登录权限-登录前缀

钩子函数的两种应用: (1). 应用在app上 before_first_request before_request after_request teardown_request (2). 应用在蓝图上 before_app_first_request #只会在第一次请求执行,往后就不执行, (待定,此属性没调试通过) before_app_request # 每次请求都会执行一次(重点…