codevs 5972 格子游戏
2024-10-21 14:19:05
5972 格子游戏
时间限制: 1 s
空间限制: 128000 KB
题目等级 : 黄金 Gold
题目描述 Description
Alice和Bob玩了一个古老的游戏:首先画一个n * n的点阵(下图n = 3) 接着,他们两个轮流在相邻的点之间画上红边和蓝边:
直到围成一个封闭的圈(面积不必为1)为止,“封圈”的那个人就是赢家。因为棋盘实在是太大了(n <= 200),他们的游戏实在是太长了!他们甚至在游戏中都不知道谁赢得了游戏。于是请你写一个程序,帮助他们计算他们是否结束了游戏?
输入描述 Input Description
输入数据第一行为两个整数n和m。m表示一共画了m条线。以后m行,每行首先有两个数字(x, y),代表了画线的起点坐标,接着用空格隔开一个字符,假如字符是"D ",则是向下连一条边,如果是"R "就是向右连一条边。输入数据不会有重复的边且保证正确。
输出描述 Output Description
输出一行:在第几步的时候结束。假如m步之后也没有结束,则输出一行“draw”。
样例输入 Sample Input
3 5
1 1 D
1 1 R
1 2 D
2 1 R
2 2 D
样例输出 Sample Output
4
数据范围及提示 Data Size & Hint
见上
这题如果用邻接矩阵做,就必须开的非常大,否则各种RE
#include<cstdio>
#include<iostream>
# define MAXN
using namespace std;
int father[MAXN];
int m,n;
int find(int x)
{
if(father[x]!=x)
{
father[x]=find(father[x]);
return father[x];
}
else
return x;
}
void unionn(int i,int j)
{
father[j]=i;
}
int main()
{
ios::sync_with_stdio(false);
cin>>n>>m;
for(int i=;i<=n*n;i++)
father[i]=i;
for(int i=;i<=m;i++)
{
int x,y;
char c;
cin>>x>>y>>c;
int r1=(x-)*n+y;
int r2;
if(c=='D')
r2=r1+n;
if(c=='R')
r2=r1+;
if(find(r1)==find(r2))
{
cout<<i;
return ;
}
else
unionn(r1,r2);
}
cout<<"draw";
return ;
}
最新文章
- Starling中通过PivotX 和 PivotY 修改原点
- 怎样制作FL Studio步进音序器中的节奏
- 3Sum——leetcode
- 【开源】Ionic项目实例《Ionic中文社区》
- Java虚拟机 - 内存模型
- BZOJ2780——[Spoj]8093 Sevenk Love Oimaster
- @RequestBody, @ResponseBody 注解详解
- HDU2457 DNA repair(AC自动机+DP)
- Eclipse 下如何引用另一个项目的Java文件
- 游戏被App Store下架 如何快速上线?
- Unity3d shader之SWAP Force Depth-of-Field Shader
- TableView基本使用
- Eclipse之文件【默认编码格式设置】,防止乱码等问题
- apigw鉴权分析(1-3)百度 AI - 鉴权方式分析
- ML笔记:Classification: Logistic Regression
- 【转】Java中的static关键字解析
- eclipse 带sts插件
- 1.	FPGA内部的逻辑资源
- Apache与php快速部署web服务
- 使用Jenkins+gitlab自动化构建时排除分支
热门文章
- [LOJ2292] [THUSC2016] 成绩单
- ThreadPoolExecutor使用错误导致死锁
- REDISTEMPLATE如何注入到VALUEOPERATIONS
- Java电商项目,秒杀,抢购等高并发场景的具体场景和一些概念以及处理思路
- 前端以及django零碎补充
- 使用layui框架根据字段来设置tr行的背景色
- Linux REDHAT 7 关闭、禁用防火墙服务
- 【hadoop】看懂WordCount例子
- SpringMVC框架笔记01_SpringMVC的使用案例和架构组件_SpringMVC和Mybatis整合_接收参数
- LFS7.10——准备Host系统