[問題] ICPC 6010

[flere (人間失格)]

想跟大家討論一下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....可是感覺跟判斷負環是一樣的道理> <






--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 180.177.7.105
※ 編輯: flere           來自: 180.177.7.105        (03/02 07:27)
→ scwg:三秒 200 個 case, graph size = 2400, 有難度..
→ flere:2400是??我這樣是不會TLE,可是會WA> <
→ DJWS:100(棋盤大小)*6(骰子底面)*4(骰子正面)
→ DJWS:分數也列入狀態就是2400*100*6*4*2(加分)*2(倒扣) 記憶體會爆
→ DJWS:上面應該是2400*4(骰子來自方向)*6(點數)*4(加分倒扣)
→ DJWS:所以記憶體應該存得下!