HDOJ 3683 Gomoku 模拟

这种模拟题是很类似于南阳ccpc国赛的铜牌题难度的

所以，想要保证拿奖，这种恶心的题还是得写出来

题目大意是：现在有个棋盘，里面有黑色和白色的棋子，五子棋的游戏规则。问你，三步之内，是不是可能出现某一方的必胜情况

分析：

A：如何判断哪方棋子先落子？

如果黑色棋子数目=白色，那么黑先落子

如果黑色棋子数目=白色棋子数目+1，那么白色先落子

其他情况，不合法

B：如何判断第一步的情况？

第一步，先落子方想要赢：只需要在棋盘上找到某一个点，使得成至少五子相连即可

C：如何判断第二步的情况？

第二步，也就是说后落子方想要赢

条件1：先落子方赢不了

条件2：后落子方需要有两个能够获胜的点（因为是博弈，所以后落子方如果只有一个获胜点，那么先落子方会堵住那个点）

D：第三步的情况

条件1：先落子方第一步赢不了，我们在棋盘上任意一个空白格子落上一个先落子方的棋子

然后就和C差不多了

所以，就落实到了两个问题：

第一个：获胜点怎么找

第二个：怎么判断当前情况是不是能够防守的（最多一个获胜点可以防守，大于一个获胜点就已经无法防守了）

#include<bits/stdc++.h>
using namespace std;

const int maxn=15;
int mp[20][20];
const int dx[]={1,1,0,-1,-1,-1,0,1};
const int dy[]={0,-1,-1,-1,0,1,1,1};
int n;

char name[10][10]={"","white","black"};

bool init(){
    scanf("%d",&n);
    if (!n) return false;
    memset(mp,0,sizeof(mp));
    int x,y,c;
    for(int i=1;i<=n;i++){
        scanf("%d%d%d",&x,&y,&c);
        mp[x+1][y+1]=c+1;
    }
    return true;
}

bool inmap(int x,int y){
    return (x>=1&&x<=maxn&&y>=1&&y<=maxn);
}

bool countandcheck(int turn,int x,int y){
    int dir,nx,ny,cnt,k;
    for(dir=0;dir<4;dir++){
        cnt=0;
        for(k=1;;++k){
            nx=x+k*dx[dir];
            ny=y+k*dy[dir];
            if (inmap(nx,ny)&&mp[nx][ny]==turn) cnt++;
            else break;
        }
        for(k=1;;++k){
            nx=x+k*dx[dir+4];
            ny=y+k*dy[dir+4];
            if (inmap(nx,ny)&&mp[nx][ny]==turn) cnt++;
            else break;
        }
        if (cnt>=4) return true;
    }
    return false;
}

bool canwin(int turn,int &x,int &y){
    for(int i=1;i<=maxn;i++)
    for(int j=1;j<=maxn;j++){
        if (mp[i][j]) continue;
        if (countandcheck(turn,i,j)){
            x=i;y=j;return true;
        }
    }
    return false;
}

bool candefend(int turn,int &x,int &y){
    int cnt=0;
    for(int i=1;i<=maxn;i++)
    for(int j=1;j<=maxn;j++){
        if (mp[i][j]) continue;
        if (countandcheck(3-turn,i,j)){
            cnt++;
            if (cnt>1) return false;
            x=i;y=j;
        }
    }
    return true;
}

void work(){
    int cnt[3],turn,x,y;
    cnt[1]=cnt[2]=0;
    for(int i=1;i<=maxn;i++)
    for(int j=1;j<=maxn;j++)
        cnt[mp[i][j]]++;
    if (cnt[1]==cnt[2]) turn=2;
    else if (cnt[1]+1==cnt[2]) turn=1;
    else{
        puts("Invalid.");
        return;
    }
    if (canwin(turn,x,y)) printf("Place %s at (%d,%d) to win in 1 move.\n",name[turn],x-1,y-1);
    else{
        if (!candefend(turn,x,y)) printf("Lose in 2 moves.\n");
        else{
            for(int i=1;i<=maxn;i++)
            for(int j=1;j<=maxn;j++)
            if (mp[i][j]==0){
                mp[i][j]=turn;
                if (!canwin(3-turn,x,y)&&!candefend(3-turn,x,y)){
                    printf("Place %s at (%d,%d) to win in 3 moves.\n",name[turn],i-1,j-1);
                    return;
                }
                mp[i][j]=0;
            }
            printf("Cannot win in 3 moves.\n");
        }
    }
}

int main(){
    //freopen("input.txt","r",stdin);
    while(init())
        work();
    return 0;
}