PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

[問題] ICPC 6010

看板Prob_Solve (計算數學 Problem Solving)作者flere (人間失格)時間11年前 (2013/03/02 07:26)推噓0(0推 0噓 6→)

留言6則, 3人參與討論串1/1

想跟大家討論一下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)