题目链接：
http://acm.hdu.edu.cn/showproblem.php?pid=5546
题目大意：
我方棋子是'x'，敌方是'o'。现在轮到我方落子，问我方能不能在下一回合吃掉对方的至少一个棋子。
吃掉的规则是：对方被围的棋子在下一回合时已经找不到为' . '的位置。
范围：棋盘大小9*9。
思路：
由于棋盘大小只有9*9，所以我们可以直接暴力枚举'o'，对于一个'o'看他四周是否已经被3个及以上的'x'占领。如果多个'o'连在一起，就将其加进去，判断的条件是这个连通块里面是否超过2个'.'，如果超过就不能吃掉棋子。否则就直接是可以了。
一个剪枝是：对于这些被访问的'o'进行标记，如果已经访问过就不再去搜了。
代码：
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;
char s[15][15];
int vis[15][15],mp[15][15],dir[4][2]={0,1,0,-1,1,0,-1,0};
int ok=0,v[100],tt,cnt;
pair<int,int>pp[100];
void dfs(int x,int y)
{
if(cnt>=2){ //如果空超过两个，就不行了。
ok=1;
return;}
if(ok)return;
for(int i=0;i<4;i++)
{
int fx,fy;
fx=x+dir[i][0];
fy=y+dir[i][1];
if(vis[fx][fy]||mp[fx][fy]==-1)continue;
if(!vis[fx][fy]){
vis[fx][fy]=1;
if(mp[fx][fy]==0){cnt++;}
if(mp[fx][fy]==1){
for(int j=1;j<=tt;j++)
{
if(!v[j]){
if(pp[j].first==fx&&pp[j].second==fy){
v[j]=1;
break;
}
}
}
dfs(fx,fy);
}
// vis[fx][fy]=0; 注意这里，搜过就不要再走回去了，否则会出现重复计数的情况
}
}
if(cnt>=2){
ok=1;
return;
}
}
int main()
{
int T,i,j,k,icase=0;
scanf("%d",&T);
while(T--)
{
icase++;
tt=0;
memset(vis,0,sizeof(vis));
memset(v,0,sizeof(v));
memset(mp,-1,sizeof(mp));
for(i=1;i<=9;i++)
for(j=1;j<=9;j++)
{
cin>>s[i][j];
if(s[i][j]=='x')mp[i][j]=-1;
if(s[i][j]=='o'){
mp[i][j]=1;
pp[++tt]=make_pair(i,j);
}
if(s[i][j]=='.')mp[i][j]=0;
}
int flag=0;
for(i=1;i<=tt;i++)
{
ok=0;
cnt=0;
if(!v[i]){
memset(vis,0,sizeof(vis));
vis[pp[i].first][pp[i].second]=1;
dfs(pp[i].first,pp[i].second);
if(ok==0){
flag=1;break;
}
v[i]=1;
}
}
printf("Case #%d: ",icase);
if(flag)printf("Can kill in one move!!!\n");
else printf("Can not kill in one move!!!\n");
}
}
/*
2
o.o...ox.
x......o.
o.xo.....
..oxo....
...o.....
.........
.......o.
o........
oox......
ooooooooo
xx.xxxxx.
xxxo.....
.........
.........
.........
.........
.........
.........
.........
...xx....
..xoox...
..xox....
....xx...
..xooo...
...xxx...
.........
.........
..x.x....
.xo.ox...
.xooox...
..xxx....
.........
.........
.........
.........
.........
*/有疑问加站长微信联系（非本文作者）
