作者flere (人間失格)
站內Prob_Solve
標題[問題] ICPC 6010
時間Sat Mar 2 07:26:19 2013
想跟大家討論一下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)
1F：→ scwg:三秒 200 個 case, graph size = 2400, 有難度.. 03/02 11:06
2F：→ flere:2400是??我這樣是不會TLE,可是會WA> < 03/02 11:11
3F：→ DJWS:100(棋盤大小)*6(骰子底面)*4(骰子正面) 03/02 20:10
4F：→ DJWS:分數也列入狀態就是2400*100*6*4*2(加分)*2(倒扣) 記憶體會爆 03/02 20:13
5F：→ DJWS:上面應該是2400*4(骰子來自方向)*6(點數)*4(加分倒扣) 03/02 20:22
6F：→ DJWS:所以記憶體應該存得下! 03/02 20:23