作者ucrxzero (RX古哥)
看板Prob_Solve
標題[問題] LeetCode上週週賽
時間Mon Nov 16 18:25:22 2020
Code:
https://tinyurl.com/yy3a5na4
問題描述:
一維座標，每次可以往右走a格，或者往左走b格，請問走到 x 最少需要幾步。
限制:
可以連續往右走無限次a
不能連續往左走兩次b
不能走到地雷座標，如果一定會碰到地雷或是走不到x，回傳-1。
解答:
1.BFS窮舉各種走法，一步一步慢慢窮舉。
2.接著記憶化走過的點。
visited[10][0] 代表10這個點用往前走的方式走過了
visited[10][1] 代表10這個點用往後走的方式走過了
問題:
為什麼記憶化搜尋的visited要二維的，不是只要一維就好了嗎?
我想說直接visited[10] = true/false，但結果這樣會過不了測資= =
我覺得有走過的點不管是來回走過都是一樣的意義呀代表你這個點的所有可能都走過了
何必再分來回的記憶化呢?在Discuss上等不到解釋，故上來發文感恩
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 43.248.19.192 (臺灣)
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Prob_Solve/M.1605522326.A.5F9.html
1F：推 FRAXIS: 因為不能連續走兩次 b? 11/16 21:49
可是這個答案已經有用一個flag去判斷你這次是不是往回走b了應該不需要在一個維度
maintain這個狀態
2F：推 LPH66: 我想你應該搞錯了第二維的意思, 那個是「你用哪步來這裡」 11/16 22:23
3F：→ LPH66: 也就是它不是在記下一步而是前一步 11/16 22:23
4F：→ LPH66: 因為問題在於你的前一步是 b 時下一步不能是 b 11/16 22:24
5F：→ LPH66: 你如果沒記著是怎麼來的話下一步會不知道該不該有 b 11/16 22:24
抱歉大大可是針對這個問題已經有用flag去判斷上一步是不是b，這樣還不夠嗎??
※ 編輯: ucrxzero (43.248.19.192 臺灣), 11/16/2020 22:49:08
6F：推 iago2007: 一個用來記錄 上一步非b最少步數 一個是上一步為b最少步 11/17 04:44
7F：→ iago2007: 數 dp式推一下就會知道這樣分不能省 11/17 04:44
8F：→ ucrxzero: 我回家拿那個測資失敗的例子推同額推看好了感謝 11/17 11:49
9F：→ ucrxzero: 我還是沒感覺 11/17 12:39
10F：→ ucrxzero: 感謝大大 11/17 12:40
11F：推 LPH66: 想到一個反例了: 往右走 2, 往左走 1, 則你走不到起點以左 11/19 18:09
12F：→ LPH66: 這在你把兩種狀態混在一起時是無法得出來的結論 11/19 18:09
13F：→ LPH66: 修正: 走不到起點左一格以左 11/19 18:10
14F：→ 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
15F：推 LPH66: 如果是這樣的思考邏輯的話, 問題點就在有些點只有左走能到 11/21 13:33
16F：→ LPH66: 但你用右蓋左的方式紀錄會把「只有左走能到」這性質也蓋掉 11/21 13:33
17F：→ LPH66: 因此在搜尋時就會去把這樣的點再往左走就錯了 11/21 13:34
18F：→ LPH66: 比較一下: 同樣用右 5 左 2 的例子, 8 和 3 的性質就不同 11/21 13:36
19F：→ LPH66: 8 可以右走到 (+5-2+5) 也可以左走到, 但 3 只能左走到 11/21 13:37
20F：→ LPH66: 所以 8 可以往左走進 6, 但 3 不能往左走進 1 11/21 13:37
21F：→ ucrxzero: 所以我們不能抹殺掉8走到6的可能 11/21 22:54
22F：→ ucrxzero: 感謝 11/21 22:54