推 Ninja5566:請問你AC跑了幾秒呢? 05/07 12:43
→ bleed1979:0.128s 已經是掛車尾的了。 05/07 15:06
以下是AC速度很慢的做法。
宣告一個struct Node內涵array A[4][3]
這代表4個方向，3個轉彎。
題目已經寫了對於每個A[y][x]最多只用一次。
為了方便不減1計算，Maze的dimension為10 x 10。
所以Node可以當成型別，宣告就是
Node Maze[10][10];
你必須在一開始就初始化Maze[10][10]為尚未標記。
在得到資料後，標記可以走和不能走。
我使用string將Maze轉成one dimension的方式，
另外加上一個紀錄路徑的one dimension string。
所以對於BFS的每一個節點，資料結構會是
struct Step {
Step(int i1, int i2, int i3,
const string& s, const string& s2)
: ny(i1), nx(i2), nd(i3), h(s), r(s2) {
}
int ny, nx, nd;
string h, r;
};
ny, nx 是座標點
nd 是方向
h 是Maze目前的標記狀況
r 是路徑，已經經過那些點
其實這題沒有什麼陷阱，但是你是RE，
我想可能要檢查一下是否有陣列索引超出範圍等等。
以上做法就參考用。
※ 引述《Ninja5566 (苦味)》之銘言：
: 開發平台(Platform): (Ex: VC++, GCC, Linux, ...)
: Devc++
: 額外使用到的函數庫(Library Used): (Ex: OpenGL, ...)
: 問題(Question)：
: http://tinyurl.com/3fztu6l
: 餵入的資料(Input)：
: uva online judge
: 預期的正確結果(Expected Output)：
: 錯誤結果(Wrong Output)：
: RE
: 程式碼(Code)：(請善用置底文網頁, 記得排版)
: http://codepad.org/1cTpVk4v
: 補充說明(Supplement)：
: 我是把一個node拆成4個部份:row col side state
: 然後做BFS
: side 指的是在N E S W哪個方向
: state指的是要出NODE還是在NODE裡面轉彎
: 所以只有在內部的NODE還有可能會有多條路(選擇轉彎方向)
: 當讀了一個row col 和一個方位+一個轉彎方向後
: 會做出這樣的三條EDGE:outnode->internode->nodeout->destnode
: internode->nodeout就是內部的node連結,index是row,col,side,0 和row,col,side,1
: 代表進入一個NODE準備要出發到其他的NODE
: 例如1,1這個NODE會變成這個樣子
: 1,1,0,1 1,1,0,0
: 1,1,3,0 1,1,1,0
: 1,1,3,1 1,1,1,1
: 1,1,2,1 1,1,2,0
: 我找得到的側資都試過沒問題 真的完全沒有頭緒 請大家幫幫忙吧
: 只有微薄1000P幣表達感謝
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.25.248.20