24h購物| | PChome| 登入
2011-06-10 21:20:24| 人氣819| 回應0 | 上一篇 | 下一篇

d914. 2. 圍棋資料庫比對

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

http://zerojudge.tw/ShowProblem?problemid=d914

內容 :

  在電腦圍棋中,為了要能找出最好的對應策咯,電腦裡經常儲存了很多著名的棋譜。這些棋譜存放在資料庫中,當玩家和電腦對弈時,電腦會將目前對弈的盤面和資料庫中的棋譜做比對,找出最相似的一個,並且參考找出來的棋譜來決定如何下。
  圍棋的棋盤是由 19 條縱線與 19 條橫線交錯所構成,如圖一所示。每一手棋都可以用三個數字(x, y, c)來表示,其中 x y 表示這一個棋子的 x 座標和 y 座標,而 c 是表示棋子顏色。我們用數字 0 表示白色,用數字 1 表示黑色。以圖一的例 子而言,他有 5 顆棋子,記錄的方法為:
  3 2 1
  9 3 0
  6 7 0
  5 4 1
  3 6 0
  記錄並無固定排列順序,黑子或白子的個數也沒有特別限定(雖然正式棋局中,黑子與白子最多各 180 枚,但是題目中卻不需要去檢查這件事),對於每個棋譜,同一個位置最多只會出現一次。

圖一(待補)

  當給定兩個棋盤後,他們的相異程度是這樣計算的。如果一個棋盤在某個座標(x, y)有棋子,不論黑子白子,而另外一個棋盤的同一個位置沒有棋子,則相異程度是 +l ;如果一個棋盤在某個座標(x, y)是黑子,而另外一個棋盤的同一個位置是白子,則相異程度是 +2 。其他情況在某個座標(x, y)的相異程度是 +0 。兩個棋盤的整梱相異程度是每個位置相異程度的總和。以圖二的例子來說,左邊棋盤在位置 (3, 2), (6, 7) 和 (9, 3) 上有棋子,而右邊棋盤在相同位置上沒有棋子,所以這些位置各自的相異程度都是 +1;反過來說,右邊棋盤在位置 (2, 3) 和 (10, 3) 上有棋子,而左邊棋盤在相同位置上沒有棋子,所以這幾個位置各自的相異程度也是 +1。位置 (3, 6) 上兩個棋盤都是白子,所以相異程度是 +0。而位置 (5, 4) 上,左邊棋盤是黑子,右邊棋盤是白子,所以相異程度是 +2。而其他沒有棋子的地方,相異程度都是 +0。 因此,兩盤棋的相異程度是 3+2+2 = 7

圖二 (待補)

輸入說明 :

第一行為一個整數 n1代表第一盤棋譜中棋子的個數,0 ≤  n1361。接下來的 n1 行,每行有三個數字,表示一個棋子的座標和顏色,數字會以一個空白隔開。再下來的一行會是另一個整數 n2,代表第二盤棋譜中棋子的個數,0 ≤  n2361。接下來的 n2 行,每行有三個數字,表示一個棋子的座標和顏色,數字會以一個空白隔開

輸出說明 :

輸出兩個棋譜的相異程度。

範例輸入 :

輸入範例 1:
2 
3 3 1
6 8 0
2
6 8 1
3 2 0

輸入範例 2:
5 
3 2 1
9 3 0
6 7 0
5 4 1
3 6 0
4
10 3 0
2 3 1
3 6 0
5 4 0

範例輸出 :

輸出範例 1:
4

輸出範例 2:
7

提示 :

出處 :

99資訊能力競賽全國決賽 (管理:pcshic)



作法 : 模擬

/**********************************************************************************/
/*  Problem: d914 "2. 圍棋資料庫比對" from 99資訊能力競賽全國決賽*/
/*  Language: C                                                                   */
/*  Result: AC (2ms, 265KB) on ZeroJudge                                          */
/*  Author: morris1028 at 2011-06-09 23:17:43                                     */
/**********************************************************************************/


#include<stdio.h>
main() {
    int N, M;
    while(scanf("%d", &N) == 1) {
        int MapN[20][20]={0}, MapM[20][20]={0};
        int a, b, c, x, y;
        for(a = 0; a < N; a++) {
            scanf("%d %d %d", &x, &y, &c);
            MapN[x][y] = c+1;
        }
        scanf("%d", &M);
        for(a = 0; a < M; a++) {
            scanf("%d %d %d", &x, &y, &c);
            MapM[x][y] = c+1;
        }
        int Ans = 0;
        for(a = 0; a < 20; a++)
            for(b = 0; b < 20; b++)
                if((MapN[a][b] == 1 && MapM[a][b] == 2) || (MapN[a][b] == 2 && MapM[a][b] ==1 ))  Ans += 2;
                else if((MapN[a][b] == 1 && MapM[a][b] == 0) || (MapN[a][b] == 2 && MapM[a][b] == 0) ||
                        (MapN[a][b] == 0 && MapM[a][b] == 1) || (MapN[a][b] == 0 && MapM[a][b] == 2))
                        Ans += 1;
        printf("%d\n",Ans);
    }
    return 0;
}

台長: Morris
人氣(819) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: 資訊競賽 |
此分類下一篇:d916. 4. 高空煙火時間限制
此分類上一篇:d913. 1. 彈珠配置

是 (若未登入"個人新聞台帳號"則看不到回覆唷!)
* 請輸入識別碼:
請輸入圖片中算式的結果(可能為0) 
(有*為必填)
TOP
詳全文