推 FRAXIS: 因為不能連續走兩次 b? 11/16 21:49
可是這個答案已經有用一個flag去判斷你這次是不是往回走b了應該不需要在一個維度
maintain這個狀態
推 LPH66: 我想你應該搞錯了第二維的意思, 那個是「你用哪步來這裡」 11/16 22:23
→ LPH66: 也就是它不是在記下一步而是前一步 11/16 22:23
→ LPH66: 因為問題在於你的前一步是 b 時下一步不能是 b 11/16 22:24
→ LPH66: 你如果沒記著是怎麼來的話下一步會不知道該不該有 b 11/16 22:24
抱歉大大可是針對這個問題已經有用flag去判斷上一步是不是b,這樣還不夠嗎??
※ 編輯: ucrxzero (43.248.19.192 臺灣), 11/16/2020 22:49:08
推 iago2007: 一個用來記錄 上一步非b最少步數 一個是上一步為b最少步 11/17 04:44
→ iago2007: 數 dp式推一下就會知道這樣分不能省 11/17 04:44
→ ucrxzero: 我回家拿那個測資失敗的例子推同額推看好了感謝 11/17 11:49
→ ucrxzero: 我還是沒感覺 11/17 12:39
→ ucrxzero: 感謝大大 11/17 12:40
推 LPH66: 想到一個反例了: 往右走 2, 往左走 1, 則你走不到起點以左 11/19 18:09
→ LPH66: 這在你把兩種狀態混在一起時是無法得出來的結論 11/19 18:09
→ LPH66: 修正: 走不到起點左一格以左 11/19 18:10
→ LPH66: 如果限向右座標的話也有反例: 往右 5 往左 2, 則走不到 1 11/19 18:12
感謝大大,我目前自己的想法是BFS在enqueue的時候,可能到達同一點的backward如果比forward快enqueue進來就不會enqueue forward的,故用一維就會消除那個點往後的可能性了。了解惹QQ,我腦筋太死以為forward一定比backward先enqueue...ORZ
※ 編輯: ucrxzero (43.248.19.192 臺灣), 11/19/2020 22:25:33
推 LPH66: 如果是這樣的思考邏輯的話, 問題點就在有些點只有左走能到 11/21 13:33
→ LPH66: 但你用右蓋左的方式紀錄會把「只有左走能到」這性質也蓋掉 11/21 13:33
→ LPH66: 因此在搜尋時就會去把這樣的點再往左走就錯了 11/21 13:34
→ LPH66: 比較一下: 同樣用右 5 左 2 的例子, 8 和 3 的性質就不同 11/21 13:36
→ LPH66: 8 可以右走到 (+5-2+5) 也可以左走到, 但 3 只能左走到 11/21 13:37
→ LPH66: 所以 8 可以往左走進 6, 但 3 不能往左走進 1 11/21 13:37
→ ucrxzero: 所以我們不能抹殺掉8走到6的可能 11/21 22:54
→ ucrxzero: 感謝 11/21 22:54