Re: [問題] Google Code Jam 2009, Round 3 - C
看板Prob_Solve (計算數學 Problem Solving)作者ledia (下班後才下棋)時間12年前 (2012/03/15 22:39)推噓1(1推 0噓 0→)留言1則, 1人參與討論串2/2 (看更多)
※ 引述《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)
推
03/15 23:26, , 1F
03/15 23:26, 1F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 2 之 2 篇)：
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
