作者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/cn.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