Python|利用BFS求表格中的最短路径

Python|利用BFS求表格中的最短路径,第1张

概述问题描述如何用BFS算法解决力扣平台上一道困难题目。给你一个m*n的网格,其中每个单元格不是 0(空)就是1(障碍物)。每一步您都可以在空白单元格中上、下、左、右移动。如果您最多可以消除k个障碍物,请找出从左上角(0,0)到右下角(m-1,n-1)的最短路径,并返回通过该路径所

问题描述

如何用BFS算法解决力扣平台上一道困难题目。给你一个 m * n 的网格,其中每个单元格不是 0(空)就是 1(障碍物)。每一步您都可以在空白单元格中上、下、左、右移动。

如果您 最多 可以消除 k 个障碍物,请找出从左上角 (0,0) 到右下角 (m-1, n-1) 的最短路径,并返回通过该路径所需的步数。如果找不到这样的路径,则返回 -1。

示例 1:

输入:
grID =
[[0,0,0],
 [1,1,0],
 [0,0,0],
 [0,1,1],
 [0,0,0]],
k = 1
输出:6
解释:
不消除任何障碍的最短路径是 10。
消除位置 (3,2) 处的障碍后,最短路径是 6 。该路径是 (0,0) -> (0,1) -> (0,2) -> (1,2) -> (2,2) -> (3,2)-> (4,2).
 示例 2:
输入:
grID =
[[0,1,1],
 [1,1,1],
 [1,0,0]],
k = 1
输出:-1
解释:
我们至少需要消除两个障碍才能找到这样的路径。

解决方案

本题我们可以设置起点q为(0,0,k),再规定一个列表d= [[0, 1], [0, -1], [1, 0], [-1, 0]]来控制移动,每经过一次障碍物k就减1,最后在m*n的矩阵里面,终点为(m-1,n-1,0),我们利用BFS广搜找出到达终点的所有结果即可,每次结果经过的点不能重复,我们规定一个集合memory来储存已经经过的点,以确保广搜的时候不会来回重复经过某一个点。

代码示例:

def shortestPath(g,k):
     r, c = len(g), len(g[0])
     d = [[0, 1], [0, -1], [1, 0], [-1, 0]]
     mem = set([(0, 0, k)])
     q = [(0, 0, k)]
     step = 0
     while q:
         n = len(q)
         for _ in range(n):
             x, y, pre = q.pop(0)#将当以前的点赋给(x,y,pre)来进行下一步。
             if x == r - 1 and y == c - 1:
                 return step
             for i, j in d:#利用BFS找出每次移动后的所有点g[nx][ny]
                 nx, ny = x + i, y + j
                 if nx >= 0 and nx  < r and ny >= 0 and ny < c:

#规定条件确保所搜点再矩阵内部
                     if g[nx][ny] == 1:#当遇到障碍物时
                         if pre and (nx,  ny, pre - 1) not in mem:
                              q.append((nx, ny, pre - 1))
                             mem.add((nx, ny, pre - 1))
                     else:
                         if (nx, ny,  pre) not in mem:
                              q.append((nx, ny, pre))
                              mem.add((nx, ny, pre))
         step += 1
     return -1

结语

本题主要考察BFS算法的运用,以及如何用代码在矩阵里进行一些移动,修改变量的 *** 作,这是笔者第一次解决力扣平台上难度为困难的题目,用了将近一下午的时间,为了能更多解决这些类似的题,还要多加练习,希望和笔者一起进步。

END

实习编辑   |   王楠岚

责       编   |   刘仕豪

 where2go 团队


   

微信号:算法与编程之美          

长按识别二维码关注我们!

温馨提示:点击页面右下角“写留言”发表评论,期待您的参与!期待您的转发!

总结

以上是内存溢出为你收集整理的Python|利用BFS求表格中的最短路径全部内容,希望文章能够帮你解决Python|利用BFS求表格中的最短路径所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错,欢迎将内存溢出网站推荐给程序员好友。

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/langs/1183560.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-06-02
下一篇 2022-06-02

发表评论

登录后才能评论

评论列表(0条)

保存