分享
hdu 5546 Ancient Go
wangkemingshishuaige · · 2809 次点击 · · 开始浏览这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。
题目连接: http://acm.hdu.edu.cn/showproblem.php?pid=5546
题意: 有两个人在一个9*9的棋盘里下棋,A 是的棋子为x , B为 o ,"." 的意思为空。 问 A的下一个 能否将 B 的棋子杀死, (跟围棋差不多)。
解题大意: dfs 判联通块的周围是否只有 一个 ‘ . ’.
#include <iostream>
#include<cstdio>
#include<cstring>
using namespace std;
char Map[20][20];
int dir[4][2]= {{1,0},{-1,0},{0,1},{0,-1}},visit[20][20],ans,ant;
void dfs(int x,int y)
{
int tx,ty,i;
visit[x][y]=ans;
for(i=0; i<4; i++)
{
tx=x+dir[i][0];
ty=y+dir[i][1];
if(Map[tx][ty]=='x')
continue;
if(tx<0||tx>=9||ty<0||ty>=9||visit[tx][ty]==ans)
continue;
if(Map[tx][ty]=='.')
{
ant++;
visit[tx][ty]=ans;
}
else
{
dfs(tx,ty);
}
}
}
int fuck()
{
int i,j;
ans=0;
for(i=0; i<9; i++)
{
for(j=0; j<9; j++)
{
if(Map[i][j]=='o'&&!visit[i][j])
{
ans++;
ant=0;
dfs(i,j);
if(ant==1)
return 1;
}
}
}
return 0;
}
int main()
{
int t,i,k;
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
scanf("%d",&t);
k=1;
getchar();
while(t--)
{
memset(visit,0,sizeof(visit));
for(i=0; i<9; i++)
{
scanf("%s",Map[i]);
}
printf("Case #%d: ",k++);
if(fuck())
printf("Can kill in one move!!!\n");
else
printf("Can not kill in one move!!!\n");
}
return 0;
}
感觉稍微吊一些的 dfs 。(模板) * - * 。
有疑问加站长微信联系(非本文作者)
入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:692541889
关注微信2809 次点击
添加一条新回复
(您需要 后才能回复 没有账号 ?)
- 请尽量让自己的回复能够对别人有帮助
- 支持 Markdown 格式, **粗体**、~~删除线~~、
`单行代码` - 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
- 图片支持拖拽、截图粘贴等方式上传
收入到我管理的专栏 新建专栏
题目连接: http://acm.hdu.edu.cn/showproblem.php?pid=5546
题意: 有两个人在一个9*9的棋盘里下棋,A 是的棋子为x , B为 o ,"." 的意思为空。 问 A的下一个 能否将 B 的棋子杀死, (跟围棋差不多)。
解题大意: dfs 判联通块的周围是否只有 一个 ‘ . ’.
#include <iostream>
#include<cstdio>
#include<cstring>
using namespace std;
char Map[20][20];
int dir[4][2]= {{1,0},{-1,0},{0,1},{0,-1}},visit[20][20],ans,ant;
void dfs(int x,int y)
{
int tx,ty,i;
visit[x][y]=ans;
for(i=0; i<4; i++)
{
tx=x+dir[i][0];
ty=y+dir[i][1];
if(Map[tx][ty]=='x')
continue;
if(tx<0||tx>=9||ty<0||ty>=9||visit[tx][ty]==ans)
continue;
if(Map[tx][ty]=='.')
{
ant++;
visit[tx][ty]=ans;
}
else
{
dfs(tx,ty);
}
}
}
int fuck()
{
int i,j;
ans=0;
for(i=0; i<9; i++)
{
for(j=0; j<9; j++)
{
if(Map[i][j]=='o'&&!visit[i][j])
{
ans++;
ant=0;
dfs(i,j);
if(ant==1)
return 1;
}
}
}
return 0;
}
int main()
{
int t,i,k;
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
scanf("%d",&t);
k=1;
getchar();
while(t--)
{
memset(visit,0,sizeof(visit));
for(i=0; i<9; i++)
{
scanf("%s",Map[i]);
}
printf("Case #%d: ",k++);
if(fuck())
printf("Can kill in one move!!!\n");
else
printf("Can not kill in one move!!!\n");
}
return 0;
}
感觉稍微吊一些的 dfs 。(模板) * - * 。