狗家店面题目

狗家店面题目
很常规的bfs找路径问题，char[][] grid上， x代表obstacle， . 代表可以走，求小车a能否从起始地到目的停车位A。
followup没有用代码实现出来，说了大概思路，留了comment就结

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

把小车b挪到最下面一排给a让出位置，把小车a停好，然后停小车b，最后返回的结果是a和b都可以停到各自的目的停车位上。

想問樓主 follow up 面試官有給點 hint 嗎？follow up 好難 QaQ  謝謝

Solumilken 发表于 2022-11-5 13:41
想問樓主 follow up 面試官有給點 hint 嗎？follow up 好難 QaQ  謝謝

面试官有让我关注obstacle的数量，但是我没有想明白。

请问LZ面的L几？店面过了吗

积分不够，看不全题目。但是觉得有点像离口 巴流司

Follow up 我有个思路但不知道复杂度会不会太高

先用bfs看a能不能到停车位A，不行就return false。如果可以，bfs的时候把能去的地方全部存起来。然后dfs b车，如果下一个move是a能到的，把它变成obstracle，然后再看能不能去到B，不能就找下一个，直到所有a能去的都不可以。O(T) = O(m^2n^2). 可以加mem记住哪条路是不能被block的

我的想法是跑4次dfs,
1.  a是否可以到A,
2. 当B是障碍，a是否可以到A.
3. b是否可以到b,
4. 当A是障碍，b是否可以到B.
那么只有当1,3成立， 然后2或者4成立， 就可以保证肯定可以成立。 时间负载度也就是4o(m*n) = o(m * n)