作者ledia (下班後才下棋)
站內Prob_Solve
標題Re: [問題] Google Code Jam 2009, Round 3 - C
時間Thu Mar 15 22:39:53 2012
※ 引述《RockLee (Now of all times)》之銘言：
: 題目敘述網址:
: http://code.google.com/codejam/contest/243103/dashboard#s=p2
: 沒有想出來如何判斷是否為 3-colorable,
: 看了當初參賽者上傳的 code 還是不太懂 ~><~
: Invader 的 code 中用來判斷是否為 3-colorable 主要為以下幾行:
: int count = 0;
: int u = pru[f1];
: while (u != pru[f2]) {u = pr[u]; count++;}
: int d = prd[f1];
: while (d != prd[f2]) {d = pr[d]; count++;}
: if (count % 2 == 1) {result = 4; break;}
: 看起來的意思似乎是, 若同一列的兩個相鄰球員間,
: 前一列在這兩個相鄰球員間的人數與後一列在這兩個相鄰球員間的人數和為奇數,
: 則非 3-colorable.
: 但我不懂的是為何這樣就可確認非 3-colorable, 例如以下三列(數字代表顏色):
: _1_2_1_
: 2_____0
: __1_2__
不能夠 3-colorable
除了 (count % 2 == 1) 之外,
還有幾個條件:
1. pru[f2] != -1, prd[f2] != -1
2. pr[f2] != -1
所以圖應該要是底下這樣的
pru[f2]->x, prd[f2]->z, pr[f2]->y
_1_2_1_x
2_____0___y
__1_2___z
試圖用 3 colors, x->2, z->1, y 就不行了
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.30.33
※ 編輯: ledia 來自: 140.112.30.33 (03/15 22:40)
1F：推 RockLee:感謝 L 大的解釋~ 03/15 23:26