Ancient Go
HDU - 5546
题意很简单，读入时用 scanf 的我，因为 getchar ( ) 就垫底了。QAQ。
代码语言：javascript复制#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <queue>
using namespace std;
int a[200][200];
int vis[200][200];
int n = 9;
struct node
{
int x, y;
} l,w;
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
void bfs(int x, int y)
{
memset(vis,0,sizeof(vis));
queue<node>q;
l.x = x;
l.y = y;
vis[x][y] = 1;
q.push(l);
while(!q.empty())
{
w = q.front();
q.pop();
for(int i = 0 ; i < 4; i )
{
int tx = dx[i] w.x;
int ty = dy[i] w.y;
if(tx >= 0 && tx < 9 && ty >= 0 && ty < 9 && vis[tx][ty] == 0 && a[tx][ty] != 'o')
{
if(a[tx][ty] == 'x')
{
vis[tx][ty] = 1;
l.x = tx;
l.y = ty;
q.push(l);
}
else if(a[tx][ty] == '.')
{
return ;
}
}
}
}
for( int i= 0; i < 9; i )
{
for(int j = 0; j < 9; j )
{
if(a[i][j]== 'x' && vis[i][j] == 1)
a[i][j] = '.';
}
}
}
int bfs1(int x,int y)
{
queue<node>q;
memset(vis,0,sizeof(vis));
w.x = x;
w.y = y;
vis[x][y] = 1;
int num = 0;
q.push(w);
while(!q.empty())
{
w = q.front();
q.pop();
for(int i = 0; i < 4; i )
{
int tx = w.x dx[i];
int ty = w.y dy[i];
if(tx >= 0 && tx < 9 && ty >= 0 && ty < 9 &&vis[tx][ty] == 0 &&a[tx][ty] != 'x' )
{
if(a[tx][ty]=='o')
{
l.x = tx;
l.y = ty;
q.push(l);
vis[tx][ty] = 1;
}
else
{
num ;
vis[tx][ty] = 1;
}
}
if(num > 1) return 0;
}
}
return 1;
}
int main()
{
int t,Case = 0;
scanf("%d", &t);
while(t--)
{
getchar();
memset(a,0,sizeof(a));
for(int i = 0; i < 9; i )
{
getchar();
for(int j = 0; j < 9; j )
{
scanf("%c", &a[i][j]);
}
}
for(int i = 0; i <9; i )
{
for(int j = 0; j < 9; j )
{
if(a[i][j] == 'x')
{
bfs(i,j);
}
}
}
int f = 0;
for(int i = 0; i < 9; i )
{
for(int j = 0; j < 9; j )
{
if(a[i][j] == 'o')
{
f = bfs1(i,j);
if(f)
{
printf("Case #%d: Can kill in one move!!!n", Case);
break;
}
}
}
if(f) break;
}
if(!f)
printf("Case #%d: Can not kill in one move!!!n", Case);
}
return 0;
}
