題目描述：
在一個15*15的棋盤上下五子棋。3步之內(nèi)誰能贏。
吐槽：
因為濫用全局變量，荒廢了一下午...
算法分析：
如果搜3步+判斷局面的話255^4 ,GG
如果搜2步，判斷制勝點225^3, 時限1s，常數(shù)大，GG
如果搜1步，判斷后手的行為(直接贏下比賽或者不讓先手贏下比賽) 225^2，AC
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int N = 15;
int x,y;
int dir[8][2] = {
{1,0} , {-1,0},
{0,1} , {0,-1},
{-1,1}, {1,-1},
{1,1} , {-1,-1}
};
inline bool jg(int X,int Y){
return X>=0 && Y >=0 && X<N && Y<N;
}
inline bool chk(int num[N][N],int c) {
x = y = -1;
int sx,sy,flag;
for(int i=0;i<N;i++)
for(int j=0;j<N;j++) if(num[i][j] == -1)
for(int p =0; p< 8; p+=2)
for(int a=0;a<5;a++){
int b = 4-a;
flag = 0;
for(int k=1;k<=a;k++){
sx = i + k * dir[p][0];
sy = j + k * dir[p][1];
if(jg(sx,sy) && num[sx][sy] == c) ; else flag = 1;
}
for(int k=1;k<=b;k++){
sx = i + k * dir[p+1][0];
sy = j + k * dir[p+1][1];
if(jg(sx,sy) && num[sx][sy] == c) ; else flag = 1;
}
if(!flag){
x = i; y = j; return 1;
}
}
return 0;
}
void OP(int num[N][N]){for(int i=0;i<N;i++) {for(int j=0;j<N;j++) if(num[i][j]==-1)cout<<"*";else cout<<num[i][j];cout<<endl;}cout<<endl;}
int dfs(int lvl, int num[N][N], int c) {
int s = chk(num,c);
if(lvl == 2 || s) {
return s;
}
if(lvl == 1) {
if(!chk(num,c^1)) return 0;
int tx = x, ty = y;
num[x][y] = c;
int S = dfs(lvl+1,num,c^1);
num[tx][ty] = -1;
if(S) return -1;
return 0;
}
int flag = 1;
for(int i=0;i<N;i++)
for(int j=0;j<N;j++) if(num[i][j] == -1){
num[i][j] = c;
int s = dfs(lvl+1,num,c^1);
num[i][j] = -1;
x = i, y = j;
if(s == -1) return 1;
flag &= s;
}
if(flag == 1) return -1;
return 0;
}
int main(){
int num[N][N];
int c,n;
while(~scanf("%d",&n) ,n) {
memset(num,-1,sizeof(num));
int suma = 0, sumb = 0, p =-1;
for(int i=0;i<n;i++){
scanf("%d%d%d",&x,&y,&c);
num[x][y] = c;
suma += c ==0;
sumb += c ==1;
}
if(suma == sumb) p = 1;
if(suma == sumb-1) p = 0;
//OP(num);
if(p == -1) {
puts("Invalid.");
continue;
}
int f = chk(num,p);
int s = dfs(0,num,p);
if(s == 0) {
puts("Cannot win in 3 moves.");
}
else if(s == 1) {
printf("Place %s at (%d,%d) to win in %s.\n",p?"black":"white",x,y,f? "1 move":"3 moves");
}
else puts("Lose in 2 moves.");
}
}
posted on 2012-07-30 21:31
西月弦 閱讀(322)
評論(0) 編輯 收藏 引用 所屬分類:
解題報告