5970 格子游戏
2018-06-17 22:50:11来源:未知 阅读 ()
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
n <= 200
分类标签 Tags 点此展开
1 #include<iostream> 2 #include<cstdio> 3 using namespace std; 4 int map[1001][1001]; 5 int now=1; 6 int f[1000001]; 7 int find(int x) 8 { 9 if(f[x]!=x) 10 f[x]=find(f[x]); 11 return f[x]; 12 } 13 void unionn(int r1,int r2) 14 { 15 f[r2]=r1; 16 } 17 int main() 18 { 19 int ans; 20 int flag=0; 21 int n,m; 22 int x1,y1; 23 int x2,y2; 24 char z; 25 cin>>n>>m; 26 for(int i=1;i<=n;i++) 27 for(int j=1;j<=n;j++) 28 { 29 map[i][j]=now; 30 now++; 31 } 32 for(int i=1;i<=n*n+20;i++) 33 f[i]=i; 34 35 //scanf("%d%d",&n,&m); 36 for(int i=1;i<=m;i++) 37 { 38 cin>>x1>>y1; 39 cin>>z; 40 if(z=='D') 41 { 42 x2=x1+1; 43 y2=y1; 44 } 45 else 46 { 47 x2=x1; 48 y2=y1+1; 49 } 50 int r1=find(map[x1][y1]); 51 int r2=find(map[x2][y2]); 52 if(r1!=r2) 53 unionn(r1,r2); 54 else 55 { 56 flag=1; 57 ans=i; 58 break; 59 } 60 61 } 62 if(flag==1) 63 cout<<ans<<endl; 64 else 65 { 66 cout<<"draw"; 67 } 68 return 0; 69 }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
下一篇:最短网络Agri-Net
- C语言实现经典游戏——扫雷! 2020-04-17
- 小游戏二之---------------五子棋 2020-03-23
- Qt5小Demo之猜数字游戏 2020-03-19
- [Uva1637][DFS][记忆化] 纸牌游戏 Double Patience 2020-03-06
- 游戏终端服务器分享(1.2版) 2020-02-11
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash