算法学社
記錄難忘的征途
posts - 141,comments - 220,trackbacks - 0

题目描述:

   在一个15*15的棋盘上下五子棋。3步之内谁能赢。

吐槽:

    因为滥用全局变量,荒废了一下午...

算法分析:

    
    如果搜3步+判断局面的话255^4 ,GG
    如果搜2步,判断制胜点225^3, 时限1s,常数大,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 西月弦 阅读(300) 评论(0)  编辑 收藏 引用 所属分类: 解题报告

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理