做题网站推荐: OpenJudge VIJOS UOJ CF JOYOI CODEVS 洛谷 RQNOJ BZOJ POJ HDU

本站题目推荐: 高精度 模拟 排序 递推 贪心 递归 搜索 动态规划 数学 图论 数据结构 实名认证 卡评测举报

输入输出 变量类型 顺序结构 选择结构 循环结构 一维数组 NOIP 资源下载


问题 2446. -- [C++一本通-图论算法]例4.8 格子游戏

2446: [C++一本通-图论算法]例4.8 格子游戏

时间限制: 1 Sec  内存限制: 128 MB
提交: 5  解决: 5
[上一题][提交][讨论版][状态][下一题]

题目描述

     Alice和Bob玩了一个古老的游戏:首先画一个n*n的点阵(图4-22中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

提示

标签

[上一题][提交][讨论版][状态][下一题]