格子游戏x(并查集)
2024-09-03 19:44:32
格子游戏
【问题描述】
Alice和Bob玩了一个古老的游戏:首先画一个n * n的点阵(下图n = 3) 接着,他们两个轮流在相邻的点之间画上红边和蓝边:
直到围成一个封闭的圈(面积不必为1)为止,“封圈”的那个人就是赢家。因为棋盘实在是太大了(n <= 200),他们的游戏实在是太长了!他们甚至在游戏中都不知道谁赢得了游戏。于是请你写一个程序,帮助他们计算他们是否结束了游戏?
【输入格式】
输入数据第一行为两个整数n和m。m表示一共画了m条线。以后m行,每行首先有两个数字(x, y),代表了画线的起点坐标,接着用空格隔开一个字符,假如字符是"D ",则是向下连一条边,如果是"R "就是向右连一条边。输入数据不会有重复的边且保证正确。
【输出格式】
输出一行:在第几步的时候结束。假如m步之后也没有结束,则输出一行“draw”。
【输入样例】
3 5
1 1 D
1 1 R
1 2 D
2 1 R
2 2 D
【输出样例】
4
#include<iostream>
#include<cstdio>
#define Maxn 2002 using namespace std; int n,m; struct zuobiao{
int x,y;
}zb[Maxn][Maxn],f1,f2; zuobiao gz(zuobiao q)
{
if(zb[q.x][q.y].x==q.x&&zb[q.x][q.y].y==q.y) return q;
zb[q.x][q.y]=gz(zb[q.x][q.y]);
return zb[q.x][q.y];
}
int main()
{
int x,y;
char zifu;
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++)//初始化操作
{
for(int j=;j<=n;j++)
{
zb[i][j].x=i;
zb[i][j].y=j;
}
}
for(int i=;i<=m;i++)
{
cin>>x>>y>>zifu;
if(zifu=='D')//down
{
f1=gz(zb[x][y]);
f2=gz(zb[x+][y]);
}
if(zifu=='R')//right
{
f1=gz(zb[x][y]);
f2=gz(zb[x][y+]);
}
if(f1.x==f2.x&&f1.y==f2.y)
{
cout<<i<<endl;
return ;
}
else zb[f1.x][f1.y]=f2;
}
cout<<"draw"<<endl;
return ;
}
最新文章
- python安装完毕后,提示找不到ssl模块的解决步骤
- 第八章 企业项目开发--分布式缓存memcached
- ios隐藏键盘
- 《JavaScript语言精粹》学习笔记
- Android:创建可穿戴应用 - 自定义布局
- 执行update操作的话,就会报“Connection is read-only. Queries leading to data modification are not allowed”的异常。
- js 向form表单中插入数据
- 第六篇 flask中session
- Linq to SQL -- Insert、Update、Delete
- 2018蓝桥杯 省赛B题(明码)
- 学习DRF之前
- JS字符串截取(获取指定字符后面的所有字符内容)
- Ubuntu 14.04 LTS 初装成
- 初识RabbitMQ
- linux shell习题
- webService上传图片
- 听听八年阿里架构师怎样讲述Dubbo和Spring Cloud微服务架构
- OO学习体会与阶段总结(多线程程序)
- linu 把文件中的字母小写转换为大写,大写转换为小写awk toupper tolower
- Linux lspci 命令
热门文章
- [转帖]linux中systemctl详细理解及常用命令
- AssertionError [ERR_ASSERTION]: Task function must be specified,gulp版本不一致
- @Select 数据表的字段与实体类的属性值
- Mysql-Sqlalchemy-增删改查分组等操作
- Fluent API
- awk--基本操作
- div+css布局教程(1)
- springboot(十九)-线程池的使用
- k-means 非监督学习聚类算法
- lambda中FirstOrDefault和First