[ZJ][DP] a365. 3. 新井字遊戲＠Morris' Blog

2012-08-16 19:50:34| 人氣1,724| 回應0 | 上一篇 | 下一篇

[ZJ][DP] a365. 3. 新井字遊戲

推薦 0 收藏 0 轉貼0 訂閱站台

內容：

在台灣宜蘭的一個小鄉鎮裡，小學生之間流傳著一個稱為『新井字』的雙人對弈遊戲。這種遊戲使用的道具是一個『井』字形的棋盤(如圖一所示)，和 12 個棋子。遊戲開始時，棋盤上每一個標示英文字母的地方，都可以隨機決定要不要擺放一個棋子(但是當然不能整個棋盤都不放棋子)。遊戲進行的規則是由兩個遊戲者輪流取走棋盤上的棋子，每人每次必須取走棋盤上任意 1 個或 2 個相鄰(棋盤上有直線相連)的棋子，而被迫取走最後一個棋子的人算輸，另一位遊戲者則得勝。

其實如果仔細思考，可以證明不管遊戲開始時的棋盤狀態(簡稱起始狀態)如何，先開始取棋子的人（先手）與其對手（後手）二人中必定恰有一人，只要他每次都用對自己最有利的方法，最後一定會得勝。舉例來說，若起始狀態中只有 A、B、F 處有棋子，則先手不管取走哪一個棋子，後手只要再移除一個棋子，就可以逼迫先手去取最後一個棋子，因此後手有百分之百得勝的把握，我們可以說『這個起始狀態是後手有利』。再舉另一個例子，若起始狀態只有 A、C、D 處有棋子，則先手只要懂得先取走 A 與 D 處相鄰的兩個棋子，就可以迫使後手去取最後一個棋子，因此先手就有百分之百得勝的把握，我們可以說『這個起始狀態是先手有利』。本題就是要請你寫一個程式，來判斷在不同的起始狀態下到底是先手還是後手有利。

輸入說明：

第一行只含一個整數 n (1 £ n £ 10)，告訴你總共有多少個起始狀態需要判斷。接下來的 n 行，每一行表示一種起始狀態。起始狀態是以連續 12 個 1 或 0 的數字來依序表示 A 到 L 的位置上有沒有棋子，1 代表該位置有棋子，0 表示該位置沒有棋子。

輸出說明：

對於輸入的每一種起始狀態，若該起始狀態為對先手有利，你的程式必須輸出一個字元 1，若對後手有利，則必須輸出一個字元 0。因為輸入總共有 n 個起始狀態，因此總共必須輸出 n 個字元在同一行，且這些字元之間不需留空白。

範例輸入： help

輸入範例 1：
1
110001000000


輸入範例 2：
2
101100000000
001100110010

範例輸出：

輸出範例 1：
0

輸出範例 2：
11

提示：

http://dl.dropbox.com/u/19301608/PIC.JPG

看不到圖片者請用上面網址

出處：

100 年全國資訊學科能力競賽 - 3 (管理：stanley17112000)

#include <stdio.h>
int main() {
    int dp[1<<12] = {};
    int i, j, state;
    int lk[24] = {1<<0,1<<1,1<<2,1<<3,1<<4,1<<5,1<<6,
                1<<7,1<<8,1<<9,1<<10,1<<11,1<<0|1<<3,
                1<<1|1<<4,1<<2|1<<3,1<<3|1<<4,1<<4|1<<5,
                1<<3|1<<7,1<<4|1<<8,1<<6|1<<7,1<<7|1<<8,
                1<<8|1<<9,1<<7|1<<10,1<<8|1<<11};
    dp[0] = 1;
    for(i = 0; i < 4096; i++) {
        for(j = 0; j < 24; j++) {
            if((i&lk[j]) == lk[j]) {
                dp[i] |= !dp[i-lk[j]];
            }
        }
    }
    int n;
    char s[50];
    while(scanf("%d", &n) == 1) {
        while(n--) {
            scanf("%s", s);
            int state = 0;
            for(i = 0; s[i]; i++)
                state += (s[i]-'0')<<i;
            printf("%d", dp[state]);
        }
        puts("");
    }
    return 0;
}

我要檢舉

#a365#3 #新井字遊戲

台長： Morris

您可能對以下文章有興趣

a094. NOI2003 Day1.1.木棒游戏

a250. NCPC2011 Problem H Special Subsequences

[ZJ][BIT] a484. 美麗風景遞增之路

b067. 6. 下棋問題

人氣(1,724) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: 資訊競賽 |
此分類下一篇:[ZJ][BIT] a484. 美麗風景遞增之路
此分類上一篇:[ZJ] d537. 第四題：染色遊戲

回應(0)