《水陆距离》题目分析
本题是一道比较简单的BFS找最短路的题目。
我们可以将NxM的每一个位置看作图中的一个点;两个点如果在矩阵中上下左右相邻,我们就在这两个点之间连一条边,长度为1。
容易看出每个点最多连出4条边,整个图是一个稀疏图。
我们将所有矩阵中的0代表的点看成起始点集,这个题就变成了求其他所有点到起始点集的最短路。
由于所有边的长度都为1,所以最短路可以用BFS求出。
我们可以把起始点集中的点都先放到BFS的队列中,BFS第一次访问到某个点时经过的步数,就是这个点距离初始点集的最短距离。
总时间复杂度是O(NM)的。
实在不会 可以去 [Offer收割]编程练习赛9 看看别人AC的代码,可以学习一下