wordpress站长主题,老域名做网站,忻州网站建设网站推广,wordpress子分页记录此题的目的#xff1a;
明确二维的坐标可以映射到一维#xff1a;在x和y都是从0开始的前提下#xff0c;假如图形列数为n#xff0c;(x,y)映射到一维可以写成x * n y。并查集并不好存储二维数据#xff0c;如果遇到二维数据可以将其映射到一维。
Alice和Bob玩了一个…记录此题的目的
明确二维的坐标可以映射到一维在x和y都是从0开始的前提下假如图形列数为n(x,y)映射到一维可以写成x * n y。并查集并不好存储二维数据如果遇到二维数据可以将其映射到一维。
Alice和Bob玩了一个古老的游戏首先画一个 n × n n×n n×n 的点阵下图 n 3 n3 n3 。
接着他们两个轮流在相邻的点之间画上红边和蓝边 直到围成一个封闭的圈面积不必为 1 1 1 为止“封圈”的那个人就是赢家。因为棋盘实在是太大了他们的游戏实在是太长了
他们甚至在游戏中都不知道谁赢得了游戏。
于是请你写一个程序帮助他们计算他们是否结束了游戏
输入格式 输入数据第一行为两个整数 n n n 和 m m m。 n n n 表示点阵的大小 m m m 表示一共画了 m m m 条线。
以后 m 行每行首先有两个数字 ( x , y ) (x,y) (x,y)代表了画线的起点坐标接着用空格隔开一个字符假如字符是 D则是向下连一条边如果是 R就是向右连一条边。
输入数据不会有重复的边且保证正确。
输出格式 输出一行在第几步的时候结束。
假如 m m m 步之后也没有结束则输出一行draw。
数据范围 1 ≤ n ≤ 200 1≤n≤200 1≤n≤200 1 ≤ m ≤ 24000 1≤m≤24000 1≤m≤24000
输入样例
3 5
1 1 D
1 1 R
1 2 D
2 1 R
2 2 D输出样例
4一道并查集的裸题。 首先游戏的结束是指有任何一部分连成了环而连成环的条件就是有一个点连上了和它连通的点也就是他们两个在同一个集合里。
主要难点考察点是如果记录数据这里采用将二维坐标映射到一维的做法。 使用公式 x ∗ ( 列数 ) y x * (列数) y x∗(列数)y
代码
#includeiostream
using namespace std;
const int N 210;int p[N * N];
int n, m;int find(int x) {if (p[x] ! x)p[x] find(p[x]);return p[x];
}int main() {cin n m;for (int i 0; i n * n1; i)p[i] i;int ans 0;bool has_answer 0;for(int i 1;i m;i) {int x, y; cin x y;x--,y--;int a x * n y; //映射到一维char op; cin op;int b;if(op D)b (x1)*n y;else b x * n y 1;if(find(a) find(b)){has_answer 1;ans i;break;}else{p[find(a)] find(b);}}if (has_answer)cout ans;else cout draw;return 0;
}
