校园网站开发,阿里巴巴国际网站官网入口,科技有限公司是什么性质,wordpress 网校主题Alice和Bob玩了一个古老的游戏#xff1a;首先画一个 nn 的点阵#xff08;下图 n3 #xff09;。
接着#xff0c;他们两个轮流在相邻的点之间画上红边和蓝边#xff1a; 直到围成一个封闭的圈#xff08;面积不必为 1#xff09;为止#xff0c;“封圈”的那个人就是…Alice和Bob玩了一个古老的游戏首先画一个 n×n 的点阵下图 n3 。
接着他们两个轮流在相邻的点之间画上红边和蓝边 直到围成一个封闭的圈面积不必为 1为止“封圈”的那个人就是赢家。因为棋盘实在是太大了他们的游戏实在是太长了他们甚至在游戏中都不知道谁赢得了游戏。 于是请你写一个程序帮助他们计算他们是否结束了游戏
输入格式 输入数据第一行为两个整数 n 和 m。n表示点阵的大小m 表示一共画了 m 条线。 以后 m 行每行首先有两个数字 (x,y)代表了画线的起点坐标接着用空格隔开一个字符假如字符是 D则是向下连一条边如果是 R 就是向右连一条边。 输入数据不会有重复的边且保证正确。
输出格式 输出一行在第几步的时候结束。 假如 m 步之后也没有结束则输出一行“draw”。
数据范围 1≤n≤2001≤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 pairint,int PII;
const int N2e610;
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;cinnm;int cnt0;for (int i1;in;i)for (int j1;jn;j)s[{i,j}]cnt;for (int i1;icnt;i) p[i]i;int a,b,x,y;char c;for (int i1;im;i){cinabc;if (cD) xa1,yb;else xa,yb1;int ls[{a,b}],rs[{x,y}];if (find(l)!find(r)) p[find(l)]find(r);else{couti;return 0;}}coutdraw;return 0;
}
