d914. 2. 圍棋資料庫比對
Tags :
Accepted rate : 320人/329人 ( 97% ) [非即時]
評分方式:
Tolerant

最近更新 : 2011-09-14 11:36

Content

  在電腦圍棋中,為了要能找出最好的對應策咯,電腦裡經常儲存了很多著名的棋譜。這些棋譜存放在資料庫中,當玩家和電腦對弈時,電腦會將目前對弈的盤面和資料庫中的棋譜做比對,找出最相似的一個,並且參考找出來的棋譜來決定如何下。
  圍棋的棋盤是由 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。

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

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

Sample Input #1
輸入範例 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
Sample Output #1
輸出範例 1:
4

輸出範例 2:
7
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (20%): 2.0s , <1M
公開 測資點#1 (20%): 2.0s , <1M
公開 測資點#2 (20%): 2.0s , <1M
公開 測資點#3 (20%): 2.0s , <1K
公開 測資點#4 (20%): 2.0s , <1M
Hint :

感谢morris1028提供图片!

Tags:
出處:
99學年度全國資訊學科能力競賽 [管理者: pcshic (PCSHIC) ]

Status Forum 排行

ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」