当前位置:网站首页>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;}
边栏推荐
猜你喜欢
随机推荐
炫酷又高效的数据可视化大屏,做起来真的没那么难!丨极客星球
树莓派入门
ECCV 2022 | 通往数据高效的Transformer目标检测器
分布式链路追踪Jaeger + 微服务Pig在Rainbond上的实践分享
什么是 DevOps?看这一篇就够了!
程序猿七夕礼物-如何30分钟给女友快速搭建专属语聊房
图像分割方法
全面认识MOS管,一篇文章就够了
如何做好企业数字化转型?这10份靠谱案例收藏了(附下载)
Matlab记录
如何过一个充满科技感的七夕?华为告诉你
MySQL - Explain详解
第10章 模块和包
年轻人为什么不喜欢买蒙牛、伊利了?
【PHP实现微信公众平台开发—基础篇】第2章 微信公众账号及申请流程详解
大神们都在用的神器,你和大神只差一个它!!
数据中台建设(九):数据中台资产运营机制
Share | technology integration electronic fence function of scheduling system
Transferring Rich Feature Hierarchies for Robust
接入华为游戏防沉迷,点击防沉迷弹窗后游戏闪退