zzuli 1732: 五子棋 (搜尋 模擬)

zzuli 1732: 五子棋 (搜尋 模擬)

1732: 五子棋

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 234  Solved: 4

SubmitStatusWeb
Board


Sample Input

2
10 10…………………..1………2…………………………………………………………
10 10……………………………1……..1………1.2………………………………………

Sample Output

other
fault

考慮下面幾種情況:
1、黑手先,則黑子和白子相等或者多一個;
2、若黑勝,則黑子比白子多一個;
3、若白勝,則白子和黑子相等;
4、雙方不能同時勝利;
最後,若存在一方勝利,則列舉這一方的所有點,把它去掉。則必存在一點,去掉後棋盤無5個連續顏色的棋子。
其他就是other。
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<iostream>
#include<math.h>
#include<vector>
using namespace std;
#define mem(a,t) memset(a,t,sizeof(a))
#define N 115
#define ll __int64
const int inf=0x1f1f1f1f;
const double eps=1e-7;
char s[N][N];
int dir[8][2]={1,1,1,0,1,-1,0,-1,-1,-1,-1,0,-1,1,0,1};
int n,m;
int judge(int x,int y) 
{
if(x>=0&&x<n&&y>=0&&y<m)
return 1;
return 0;
}
int bfs(int f)      //判斷f方是否存在5子連續
{
char tmp=f '0';
int i,j,k,cnt,x,y;
for(i=0;i<n;i  )
{
for(j=0;j<m;j  )
{
if(s[i][j]==tmp)
{
for(k=0;k<8;k  )
{
x=i;
y=j;
cnt=1;
while(1)
{
x =dir[k][0];
y =dir[k][1];
if(!judge(x,y)||s[x][y]!=tmp)
break;
cnt  ;
}
if(cnt>=5)
return 1;
}
}
}
}
return 0;
}
void fun(int f)    //去掉一子
{
int i,j,flag=0;
char tmp=f '0';
for(i=0;i<n;i  )
{
for(j=0;j<m;j  )
{
if(s[i][j]==tmp)
{
s[i][j]='0';
if(bfs(f)==0)
{
flag=1;
break;
}
s[i][j]=tmp;
}
}
if(flag)
break;
}
if(flag)
{
if(f==1)
printf("white\n");
else
printf("black\n");
}
else
printf("fault\n");
}
int main()
{
int i,j,T;
int b,w;
int f1,f2;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&m);
b=w=0;
for(i=0;i<n;i  )
{
scanf("%s",s[i]);
for(j=0;j<m;j  )
{
if(s[i][j]=='1')
w  ;
else if(s[i][j]=='2')
b  ;
}
}
if(b!=w&&b!=w 1)
{
printf("fault\n");
continue;
}
f1=bfs(1);
f2=bfs(2);
if(f1&&f2)
{
printf("fault\n");
continue;
}
if(f1)
{
if(w!=b)
printf("fault\n");
else
fun(1);
}
else if(f2)
{
if(b!=w 1)
printf("fault\n");
else
fun(2);
}
else
printf("other\n");
}
return 0;
}