hiho一下第236周《水陆距离》题目分析

1
0

《水陆距离》题目分析

本题是一道比较简单的BFS找最短路的题目。

我们可以将NxM的每一个位置看作图中的一个点;两个点如果在矩阵中上下左右相邻,我们就在这两个点之间连一条边,长度为1。

容易看出每个点最多连出4条边,整个图是一个稀疏图。

我们将所有矩阵中的0代表的点看成起始点集,这个题就变成了求其他所有点到起始点集的最短路。

由于所有边的长度都为1,所以最短路可以用BFS求出。

我们可以把起始点集中的点都先放到BFS的队列中,BFS第一次访问到某个点时经过的步数,就是这个点距离初始点集的最短距离。

总时间复杂度是O(NM)的。

1 answer(s)

1

不会

  • 实在不会 可以去 [Offer收割]编程练习赛9 看看别人AC的代码,可以学习一下

  • 添加评论
  • reply

write answer 切换为英文 切换为中文


转发分享