UVA10838 The Pawn Chess

UVA好题没人写系列，感觉可以稍稍练习一下面向对象编程的形式（大雾）

题意很简单，在国际象棋的棋盘中有一些兵，走到对方底线即为胜利，问最优决策下谁能获胜。并输出最小步数。

首先这里的棋盘都只有\(4\times 4\)，意味这状态很小。

所以我们可以联想到用类似于Luogu P4576 [CQOI2013]棋盘游戏用对抗搜索的方式求解。

如果可以获胜就找最小步数，否则要失败的那一方应该找一个能苟活最久的状态走下去。

发现这个决策其实就是取\(\min,\max\)，这里显然也可以记忆化，但状态数\(3^{16}\)加上多组数据实在带不动。

这个时候我们只能掏出对抗搜索的神奇剪枝了——\(alpha-beta\)剪枝。

原理和模板可以自行百度，其实就是一种最优性剪枝。

注意合理的实现方式，否则可能会让代码又臭又长。

CODE

#include<cstdio>

#include<vector>

#define RI register int

#define pb push_back

using namespace std;

const int N=4,INF=1e9;

struct status

{

    char a[N+1][N+1]; //0 white turn,1 black turn

    inline int isover(void)

    {

        for (RI i=0;i<N;++i)

        {

            if (a[0][i]=='P') return 0;

            if (a[3][i]=='p') return 1;

        } return -1;

    }

    inline void expand(int player,vector <status> &next)

    {

        if (!player)

        {

            for (RI i=1;i<4;++i) for (RI j=0;j<4;++j) if (a[i][j]=='P')

            {

                if (a[i-1][j]=='.') { status to=*this; to.a[i-1][j]='P'; to.a[i][j]='.'; next.pb(to); }

                if (j&&a[i-1][j-1]=='p') { status to=*this; to.a[i-1][j-1]='P'; to.a[i][j]='.'; next.pb(to); }

                if (j<3&&a[i-1][j+1]=='p') { status to=*this; to.a[i-1][j+1]='P'; to.a[i][j]='.'; next.pb(to); }

            }

        } else

        {

            for (RI i=0;i<3;++i) for (RI j=0;j<4;++j) if (a[i][j]=='p')

            {

                if (a[i+1][j]=='.') { status to=*this; to.a[i+1][j]='p'; to.a[i][j]='.'; next.pb(to); }

                if (j&&a[i+1][j-1]=='P') { status to=*this; to.a[i+1][j-1]='p'; to.a[i][j]='.'; next.pb(to); }

                if (j<3&&a[i+1][j+1]=='P') { status to=*this; to.a[i+1][j+1]='p'; to.a[i][j]='.'; next.pb(to); }

            }

        }

    }

}st; int t;

inline int AlphaBeta_Search(status now,int step,int player,int alpha,int beta)

{

    int res=now.isover(); if (!res) return INF-step; if (~res) return step-INF;

    vector <status> next; next.clear(); now.expand(player,next);

    int lim=next.size(); if (!lim) return player?INF-step:step-INF;

    for (RI i=0;i<lim;++i)

    {

        res=AlphaBeta_Search(next[i],step+1,player^1,alpha,beta);

        if (player) beta=res<beta?res:beta; else alpha=res>alpha?res:alpha;

        if (beta<=alpha) break;

    }

    return player?beta:alpha;

}

int main()

{

    for (scanf("%d",&t);t;--t)

    {

        for (RI i=0;i<4;++i) scanf("%s",st.a[i]);

        int res=AlphaBeta_Search(st,0,0,-2*INF,2*INF); //res<0 means black will win

        if (res<0) printf("black (%d)\n",res+INF); else printf("white (%d)\n",-res+INF);

    }

    return 0;

}

巴特西

UVA10838 The Pawn Chess

最新文章

热门文章