想跟大家討論一下ICPC 6010 這一題的作法
題目網址 : http://ppt.cc/fHLE
這一題看起來不難
可是比賽場上沒有隊伍過OAO
ICPC上面過的人也極少
所以我在想一定有些什麼地方我沒弄懂或誤會了OAQ
以下是題意:
給一個最大10*10的棋盤
"S"代表起始位置,"T"代表終點位置
"."不能走
"0"~"9"代表數字,可以走
現在給你一顆骰子(會給你他的長相,上面有哪些數字(只會出現1-6
比如說給你123465代表(右左前後上下
現在你要開始滾動這顆骰子從S到T
當你壓到的數字跟你骰子底下的數字一樣時,比如說都是5
這時你的分數可以加上(5+5)
當你壓到的數字跟你的底部不一樣時,假設你壓到3,然後骰子底部是5
這時分數要扣(3+5)
起點S一旦離開就不能再走進去
一旦走到終點就結束
其他數字點皆可以無限走
問說
可以到終點嗎?
可以的話最高能拿幾分?
可以無限洗分嗎??
以下是我的作法
step 1 : 我先從S做一次BFS看能不能到T,這邊不行的話就可以直接輸出impossible
step 2 : 把起點S標記成牆壁,因為他走出去之後就相當於變成牆壁了,這時從
終點T做一次BFS,看終點在S變成牆壁時可以走到那些點
所以之後滾動就只滾那些點就好了
不然有可能你走到一個地方分數能變高,但是因為起點不能重複走而走不到終點的情況
step 3 : 開始滾動,我用SPFA的作法從起點開始,若有一個點被更新超過(N*M)次,
表示偵測到正環->輸出infinity
然後我記錄的狀態是
state[][][][][],前3格是骰子的樣子,後兩格為棋盤上的位置
不知道這樣的方法哪邊會出現問題??
還是各位有別的不同的想法嗎??
感覺最不正確的是step 3....可是感覺跟判斷負環是一樣的道理> <