讨论/技术交流/求助|虾皮 3.10 笔试题/
求助|虾皮 3.10 笔试题

假设一个矩阵里面有 0011 求从第一行某个点出发到走完所有 11 的点所需的最小步数。

4
共 11 个回复

转成图然后参考 847. 访问所有节点的最短路径

1

选中第一行一个点,然后找他周围最近的未被选的点,连起来,再由这个点重复以上操作。这种方法是对一个选中的点的最优方案。不过我不晓得怎么加快,只能枚举第一行的点。选的过程可以加快。这是我目前想的最好方法了,但感觉还是不太行。我再想想

1

给个测试用例

看到最小先想到 bfs

该内容已被删除

不对吧,比如只有第一列和最后一列是1,这种极端情况,就不是逐行了

这个是np问题吧,指定路径了。用贪心算法做?找到剩下没走的最近的1走。
动态规划只能解决有多少种走法?

冒个泡泡

数据范围多少

动态规划?

回溯?广度遍历