当前位置:网站首页>Motion Rule (16)-Union Check Basic Questions-Grid Game
Motion Rule (16)-Union Check Basic Questions-Grid Game
2022-08-04 12:33:00 【H_Cisco】
[Problem description]
Aliceand Bobplayed an old game: draw one firstn * n lattice (belown= 3) Then, the two of them take turns to draw between adjacent dotsRed and blue borders:
until a closed circle (the area does not have to be 1), the person who "closes" is the winner.Because the board is so big(n<= 200), their game is reallyis too long!They don't even know who won the game in the game.So please write a program to help them figure out if they're over the game?
[input format]
The first line of input data is two integersnandm.mindicates that a total of mlines.After mlines, each line starts with two numbers(x,y), which represents the starting point coordinates of the line, and then separate a character with a space, if the character is"D ", it is a downward connection, if it is "R" is to connect a side to the right.The input data will not have duplicate edges and is guaranteed to be correct.
[Output format]
Output a line: end at the first step.If m does not end after the step, output a line "
[Sample input]
3 5
1 1 D
1 1 R
1 2 D
2 1 R
2 2 D
[Example output]
4
#include #include using namespace std;int fa[40001], n, m, x, y, r1, r2, xx, yy;char ch;int find(int u){return fa[u] == u ? u : fa[u] = find(fa[u]);}int read(){int x = 0;char ch = getchar();while (!isdigit(ch))ch = getchar();while (isdigit(ch))x = x * 10 + ch - 48, ch = getchar();return x;}int main(){cin >> n >> m;for (int i = 1; i <= n * n; i++)fa[i] = i;for (int i = 1; i <= m; i++){x = read();y = read();cin >> ch;xx = n * (x - 1) + y;if (ch == 'D')yy = xx + n;elseyy = xx + 1;r1 = find(xx);r2 = find(yy);if (r1 != r2)fa[r1] = r2;else{cout << i;return 0;}}cout << "draw" << endl;return 0;}
边栏推荐
猜你喜欢
动规(16)-并查集基础题——格子游戏
2022上半年各银行理财子公司深耕差异化发展,净值型产品数量增加
情人节浪漫3D照片墙【附源码】
DC/DC电感底部要不要覆铜?
How to develop small program plug-ins to achieve profitability?
涨姿势了!原来这才是多线程正确实现方式
Flutter使用 json_serializable 解析 JSON 最佳方案
【全网首发】Redis系列5:深入分析Cluster 集群模式
A comprehensive understanding of MOS tubes, an article is enough
ECCV 2022 | Towards Data Efficient Transformer Object Detectors
随机推荐
matlab串口读写
程序猿七夕礼物-如何30分钟给女友快速搭建专属语聊房
记我的第一篇CCF-A会议论文|在经历六次被拒之后,我的论文终于中啦,耶!
Transferring Rich Feature Hierarchies for Robust
【VBox】解决复制VBox虚拟机后提示硬盘UUID 已经存在的问题
涨姿势了!原来这才是多线程正确实现方式
集群监控——Zabbix
Shell loop statement (for, while, until)
Focus!2022 interview must brush 461 interview questions summary + interview + resume template
绩效考核带给员工的不能只是压力
分布式链路追踪Jaeger + 微服务Pig在Rainbond上的实践分享
Redis(一)安装与配置
Cool and efficient data visualization big screen, it's really not that difficult to do!丨Geek Planet
业务中我们如何更新缓存?Redis
从数学角度和编码角度解释 熵、交叉熵、KL散度
Tapdata 开源项目基础教程:功能特性及实操演示
shell之循环语句(for、while、until)
活动报名:如何高效应对当下的实时场景需求?
动规(16)-并查集基础题——格子游戏
backbone核心详解系列——RepVGG