d914. 2. 圍棋資料庫比對
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。
圖二 (待補)
輸入說明
:
輸出說明
:
輸出兩個棋譜的相異程度。
範例輸入 :
輸入範例 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
提示
:
出處
:
/**********************************************************************************/
/* 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;
}
上一篇:d913. 1. 彈珠配置