The 2015 China Collegiate Programming Contest G. Ancient Go hdu 5546
Ancient Go
Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 65535/65535 K (Java/Others)
Total Submission(s): 577 Accepted Submission(s): 213
Here is the rules for ancient go they were playing:
⋅The game is played on a 8×8 cell board, the chess can be put on the intersection of the board lines, so there are 9×9 different positions to put the chess.
⋅Yu Zhou always takes the black and Su Lu the white. They put the chess onto the game board alternately.
⋅The chess of the same color makes connected components(connected by the board lines), for each of the components, if it's not connected with any of the empty cells, this component dies and will be removed from the game board.
⋅When one of the player makes his move, check the opponent's components first. After removing the dead opponent's components, check with the player's components and remove the dead components.
One day, Yu Zhou was playing ancient go with Su Lu at home. It's Yu Zhou's move now. But they had to go for an emergency military action. Little Qiao looked at the game board and would like to know whether Yu Zhou has a move to kill at least one of Su Lu's chess.
.......xo
.........
.........
..x......
.xox....x
.o.o...xo
..o......
.....xxxo
....xooo.
......ox.
.......o.
...o.....
..o.o....
...o.....
.........
.......o.
...x.....
........o
Case #2: Can not kill in one move!!!
In the first test case, Yu Zhou has 4 different ways to kill Su Lu's component.
In the second test case, there is no way to kill Su Lu's component.
#include <iostream>
#include <cstdio>
using namespace std; const int n = ;
const int dx[] = {-, , , }, dy[] = {, -, , };
int map[n][n];
int visit[n][n], flagcnt; inline bool Check(int x, int y)
{
if(x < || x >= n || y < || y >= n) return ;
return ;
} inline bool Search(int x, int y)
{
if(map[x][y] == ) return ;
if(map[x][y] == ) return ;
visit[x][y] = flagcnt;
for(int k = ; k < ; k++)
{
int tx = x + dx[k], ty = y + dy[k];
if(Check(tx, ty) && visit[tx][ty] != flagcnt)
{
if(Search(tx, ty))
return ;
}
}
return ;
} inline void Solve()
{
for(int i = ; i < ; i++)
for(int j = ; j < ; j++)
{
char ch = ' ';
while(ch != '.' && ch != 'x' && ch != 'o') ch = getchar();
if(ch == '.') map[i][j] = ;
else if(ch == 'o') map[i][j] = ;
else if(ch == 'x') map[i][j] = ;
} for(int i = ; i< ; i++)
for(int j = ; j < ; j++)
if(map[i][j] == )
{
map[i][j] = ;
for(int k = ; k < ; k++)
{
int x = i + dx[k], y = j + dy[k];
if(Check(x, y) && map[x][y] == )
{
++flagcnt;
if(!Search(x, y))
{
printf("Can kill in one move!!!\n");
return;
}
}
}
map[i][j] = ;
}
printf("Can not kill in one move!!!\n");
} int main()
{
int test;
scanf("%d", &test);
for(int testnumber = ; testnumber <= test; testnumber++)
{
printf("Case #%d: ", testnumber);
Solve();
}
return ;
}
最新文章
- Leonbao:MapKit学习笔记
- 洛谷 P1019 单词接龙 Label:dfs
- (转)JAVA 调用matlab
- Android 优秀UI控件 ---- FlowingDrawer
- 关于IllegalMonitorStateException异常
- memcached简介(转)
- 逻辑运算符||和| 、&;&;和&;的区别
- 写一个MyORM--利用反射的方法
- 畅通工程再续--hdu1875
- 联想企业网盘:SaaS服务集群化持续交付实践
- JS面向对象基础2
- python基础===随机打印txt文件中的某一行
- [每天一个Linux小技巧] 强制让内核按单核模式启动
- 展示博客(Beta版本)
- 你不知道的JavaScript--Item6 var预解析与函数声明提升(hoist )
- Java部分概念理解
- Android 展示控件之Surface、SurfaceView、SurfaceHolder及SurfaceHolder.Callback之间的关系
- 莫烦scikit-learn学习自修第二天【算法地图】
- springcloud-知识点总结(三):Hystrix &; Dashboard &; turbine &; Zuul &; SpringCloud Config
- 模拟实现strncpy,strncat,strncmp
热门文章
- ASP.NET SignalR 与 LayIM2.0 配合轻松实现Web聊天室(一) 之 基层数据搭建,让数据活起来(数据获取)
- DB2 for z: system catalog tables
- hdu 5018 Revenge of Fibonacci
- hud 2602 Bone Collector
- 三、jQuery--jQuery基础--jQuery基础课程--第2章 jQuery 基础选择器
- Android自学指导
- max number of threads [1024] for user [lish] likely too low, increase to at least [2048]
- CLR via C#(14)-可空值类型,关于?和??的故事
- Android画面显示原理
- Delphi中的异常处理