傳送門(mén)：windy和水星 -- 水星游戲 1

題意：在一張由 n*m 的格子組成的棋盤(pán)上放著 k 個(gè)騎士每個(gè)騎士的位置為(xi,yi)，表示第xi行，第yi列騎士如果當(dāng)前位置為(x,y),一步可以走的位置為

(x-2,y-1)

(x-2,y+1)

(x-1,y-2)

(x+1,y-2)

兩人對(duì)弈，每次移動(dòng)一個(gè)騎士，在同一時(shí)間可有多個(gè)騎士在同一格子，誰(shuí)不能移動(dòng)誰(shuí)輸現(xiàn)在給定初始棋面，問(wèn)先手是否有必勝的策略？

分析：將k個(gè)騎士當(dāng)成k個(gè)子游戲，然后求出k個(gè)子游戲的sg值，然后問(wèn)題轉(zhuǎn)換成有k堆石子，每堆有sg[i]個(gè)石子，先手可以選擇一堆取1~sg[i]個(gè)石子，取完最后的石子的人贏，這就變成裸Nim游戲，將所有sg值異或判斷是否為0即可。

#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 110
using namespace std;
int n,m,k;
int sg[N][N];
int dx[]={-2,-2,-1,1};
int dy[]={-1,1,-2,-2};
bool judge(int a,int b)
{
    return a>=0&&a<n&&b>=0&&b<m;
}
int dfs(int x,int y)
{
    if(~sg[x][y])return sg[x][y];
    int vis[5],temp;
    memset(vis,false,sizeof(vis));
    for(int i=0;i<4;i++)
    {
        int a=x+dx[i],b=y+dy[i];
        if(!judge(a,b))continue;
        if((temp=sg[x][y])==-1)temp=dfs(a,b);
        vis[temp]=1;
    }
    for(int i=0;i<5;i++)
    {
        if(vis[i])continue;
        return sg[x][y]=i;
    }
}
int main()
{
    while(scanf("%d%d%d",&n,&m,&k)>0)
    {
        memset(sg,-1,sizeof(sg));
        sg[0][0]=sg[0][1]=sg[1][0]=sg[1][1]=0;
        for(int i=0;i<n;i++)
            for(int j=0;j<m;j++)
            if(sg[i][j]==-1)dfs(i,j);
        int x,y,flag=0;
        while(k--)
        {
            scanf("%d%d",&x,&y);
            flag^=sg[x][y];
        }
        if(flag)puts("yes");
        else puts("no");
    }
}

View Code

總結(jié)

以上是生活随笔為你收集整理的SCU 3132（博弈）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。