當前位置 主頁 > 服務器問題 > Linux/apache問題 > 最大化 縮小

    C++實現涂色游戲(博弈)

    欄目:Linux/apache問題 時間:2020-02-05 22:01

    在一個2*N的格子上,Alice和Bob又開始了新游戲之旅。 

    這些格子中的一些已經被涂過色,Alice和Bob輪流在這些格子里進行涂色操作,使用兩種涂色工具,第一種可以涂色任意一個格子,第二種可以涂色任意一個2*2的格子。每一輪游戲里,他們可以選擇一種工具來涂色尚未被染色的格子。需要注意,涂色2*2的格子時,4個格子都應當未被涂色。最后一步涂滿所有格子的玩家獲勝。 

    一如既往,Alice先手,最優策略,誰是贏家? 
    Input輸入第一行為T,表示有T組測試數據。 
    每組數據包含兩個數字,N與M,M表示有多少個已被染色的格子。接下來的M行每行有兩個數字Xi與Yi,表示已經被涂色的格子坐標。 

    [Technical Specification] 

    1. 1 <= T <= 74 
    2. 1 <= N <= 4747 
    3. 0 <= M <= 2 * N 
    4. 1 <= Xi <= 2, 1 <= Yi <= N,格子坐標不會重復出現 
    Output對每組數據,先輸出為第幾組數據,然后輸出“Alice”或者“Bob”,表示這輪游戲的贏家。 Sample Input
    2
    2 0
    2 2
    1 1
    2 2
    Sample Output
    Case 1: Alice
    Case 2: Bob

    思路:

    可以先考慮有連續n列的空格的sg值是多少。

    n=0時顯然sg[0]=0,之后就是普通的sg函數打表,只不過是要將格子分區而已。

    #include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <string>
    #include <cmath>
    #include <queue>
    #include <algorithm>
    #include <vector>
    #include <stack>
    #define INF 0x3f3f3f3f
    #pragma comment(linker, "/STACK:102400000,102400000")
    using namespace std;
    const int maxn=5000;
    int sg[maxn];
    bool pl[2][maxn];
    int get_sg(int x)
    {
     if(sg[x]!=-1)
      return sg[x];
     bool vis[maxn];
     memset(vis, false , sizeof(vis));
     for(int i=0; i<=x-1-i; i++)
     {
      int t=get_sg(i)^1^get_sg(x-1-i); //只涂這一列的其中一個格子
      vis[t]=true;
     }
     for(int i=0; i<=x-2-i; i++)
     {
      int t=get_sg(i)^get_sg(x-i-2); //這一列的格子都涂
      vis[t]=true;
     }
     for(int i=0; ; i++)
     {
      if(!vis[i])
      {
       sg[x]=i;
       break;
      }
     }
     return sg[x];
    }
    int main()
    {
     memset(sg, -1, sizeof(sg));
     sg[0]=0;
     for(int i=1; i<maxn; i++)
      sg[i]=get_sg(i);
     int t;
     scanf("%d", &t);
     for(int cas=1; cas<=t; cas++)
     {
      int n, m;
      scanf("%d%d", &n, &m);
      memset(pl, false, sizeof(pl));
      int ans=0;
      for(int i=1; i<=m; i++)
      {
       int x, y;
       scanf("%d%d", &x, &y);
       pl[--x][--y]=true; 
      }
      int cnt=0;
      for(int i=0; i<n; i++) //將格子分區
      {
       if(pl[0][i]&&pl[1][i])  //如果某一列的格子都涂了,那么異或這一列格子之前的連續空格子的sg值
       {
        ans^=sg[cnt];
        cnt=0;
        continue;
       }
       if(pl[0][i]^pl[1][i]) //如果這一列之涂了一個格子,那么異或這一列格子之前的連續空格子的sg值再異或1
       {
        ans=ans^sg[cnt]^1;
        cnt=0;
        continue;
       }
       cnt++;  //如果這一列沒有格子被涂,那么連續空格子的長度+1
      }
      ans^=sg[cnt];
      if(ans)
       printf("Case %d: Alice\n", cas);
      else
       printf("Case %d: Bob\n", cas);
     }
     return 0;
    }

    以上就是本文的全部內容,希望對大家的學習有所幫助,也希望大家多多支持IIS7站長之家。

    下一篇:沒有了
777亚洲人成视频免费视频