怎么使用C++實(shí)現(xiàn)涂色游戲-創(chuàng)新互聯(lián)

這篇文章給大家分享的是有關(guān)怎么使用C++實(shí)現(xiàn)涂色游戲的內(nèi)容。小編覺(jué)得挺實(shí)用的，因此分享給大家做個(gè)參考，一起跟隨小編過(guò)來(lái)看看吧。

成都創(chuàng)新互聯(lián)公司堅(jiān)持“要么做到，要么別承諾”的工作理念，服務(wù)領(lǐng)域包括：成都網(wǎng)站設(shè)計(jì)、成都做網(wǎng)站、企業(yè)官網(wǎng)、英文網(wǎng)站、手機(jī)端網(wǎng)站、網(wǎng)站推廣等服務(wù)，滿足客戶于互聯(lián)網(wǎng)時(shí)代的陜西網(wǎng)站設(shè)計(jì)、移動(dòng)媒體設(shè)計(jì)的需求，幫助企業(yè)找到有效的互聯(lián)網(wǎng)解決方案。努力成為您成熟可靠的網(wǎng)絡(luò)建設(shè)合作伙伴！

在一個(gè)2*N的格子上，Alice和Bob又開(kāi)始了新游戲之旅。

這些格子中的一些已經(jīng)被涂過(guò)色，Alice和Bob輪流在這些格子里進(jìn)行涂色操作，使用兩種涂色工具，第一種可以涂色任意一個(gè)格子，第二種可以涂色任意一個(gè)2*2的格子。每一輪游戲里，他們可以選擇一種工具來(lái)涂色尚未被染色的格子。需要注意，涂色2*2的格子時(shí)，4個(gè)格子都應(yīng)當(dāng)未被涂色。最后一步涂滿所有格子的玩家獲勝。

一如既往，Alice先手，最優(yōu)策略，誰(shuí)是贏家？
Input輸入第一行為T，表示有T組測(cè)試數(shù)據(jù)。
每組數(shù)據(jù)包含兩個(gè)數(shù)字，N與M，M表示有多少個(gè)已被染色的格子。接下來(lái)的M行每行有兩個(gè)數(shù)字Xi與Yi，表示已經(jīng)被涂色的格子坐標(biāo)。

[Technical Specification]

1. 1 <= T <= 74
2. 1 <= N <= 4747
3. 0 <= M <= 2 * N
4. 1 <= Xi <= 2, 1 <= Yi <= N，格子坐標(biāo)不會(huì)重復(fù)出現(xiàn)
Output對(duì)每組數(shù)據(jù)，先輸出為第幾組數(shù)據(jù)，然后輸出“Alice”或者“Bob”，表示這輪游戲的贏家。 Sample Input
2
2 0
2 2
1 1
2 2
Sample Output
Case 1: Alice
Case 2: Bob

思路：

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

n=0時(shí)顯然sg[0]=0，之后就是普通的sg函數(shù)打表,只不過(guò)是要將格子分區(qū)而已。

#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); //只涂這一列的其中一個(gè)格子
  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++) //將格子分區(qū)
  {
   if(pl[0][i]&&pl[1][i])  //如果某一列的格子都涂了，那么異或這一列格子之前的連續(xù)空格子的sg值
   {
    ans^=sg[cnt];
    cnt=0;
    continue;
   }
   if(pl[0][i]^pl[1][i]) //如果這一列之涂了一個(gè)格子，那么異或這一列格子之前的連續(xù)空格子的sg值再異或1
   {
    ans=ans^sg[cnt]^1;
    cnt=0;
    continue;
   }
   cnt++;  //如果這一列沒(méi)有格子被涂，那么連續(xù)空格子的長(zhǎng)度+1
  }
  ans^=sg[cnt];
  if(ans)
   printf("Case %d: Alice\n", cas);
  else
   printf("Case %d: Bob\n", cas);
 }
 return 0;
}

感謝各位的閱讀！關(guān)于“怎么使用C++實(shí)現(xiàn)涂色游戲”這篇文章就分享到這里了，希望以上內(nèi)容可以對(duì)大家有一定的幫助，讓大家可以學(xué)到更多知識(shí)，如果覺(jué)得文章不錯(cuò)，可以把它分享出去讓更多的人看到吧！

另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)建站www.muchs.cn，海內(nèi)外云服務(wù)器15元起步，三天無(wú)理由+7*72小時(shí)售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國(guó)服務(wù)器、虛擬主機(jī)、免備案服務(wù)器”等云主機(jī)租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡(jiǎn)單易用、服務(wù)可用性高、性價(jià)比高”等特點(diǎn)與優(yōu)勢(shì)，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場(chǎng)景需求。

名稱欄目：怎么使用C++實(shí)現(xiàn)涂色游戲-創(chuàng)新互聯(lián)
瀏覽地址：http://www.muchs.cn/article20/cshpjo.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供定制網(wǎng)站、網(wǎng)站內(nèi)鏈、網(wǎng)站制作、移動(dòng)網(wǎng)站建設(shè)、做網(wǎng)站、靜態(tài)網(wǎng)站

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源：創(chuàng)新互聯(lián)

猜你還喜歡下面的內(nèi)容