【算法分析】 求最少需要多少步，考虑使用广搜。从起点开始进行搜索，规则只能向上下左右走动，当搜索到终点时就结束。 【参考代码】 【时间复杂度】 O(n∗m)O(n*m)O(n∗m) 【预计得分】 100pts100pts100pts

起点也是点。

1. 广搜： 2. 深搜（TLE)： 3.骗分：

双向广搜： 顾名思义，就是一边从头搜，一边从尾搜 它可以减少时间复杂度，但有几率增加空间复杂度 先初始化和输入 （这步不用教吧） 接下来，由于要两边一起来，所以要弄2个队列（q1,q2)和2个标记数组(v1,v2（在上面）) 然后就是本解法的华点： 当两边有一端无路可走时，就结束了 然后，优先解决队列中较多的那一头 剩下的就和正常广搜一样了 最后，献上完整代码，请勿直接搬运，抄袭可耻

十分感谢@注释对本题解的贡献

正确题解

题目大意 求从（1,1）到（R,C）所需的最短步数。 思路 广搜。 哦我不会广搜 还有什么解法呢……动态规划！从这个点四周所需步数最少的点走过来就能得到这个点的最优解。 设当前状态dp[i][j]为走到该格所需的最小步数，则状态转移方程为 于是喜提90。 花了一个探照灯得知，有些时候某个点的实际最优可能是由 ,也就是右边来的，而此时右边还没有访问，于是只能……再从右往左遍历一遍了。 （也许还有更好的方法，但实在想不出来了） 代码： 记得将每个点初始化为极大值，还有别忘了障碍物！ 谁会傻到把它忘了 模仿洛谷的题解风格写的，求赞

啊吧啊吧 看注释吧，广搜写法

/只因AC实在太美/ 仅供参考请勿抄袭

}