倒水问题 bfs (例:uva 10603)_有a、b、c三个杯子,容量分别为3升、7升和10升,三个杯子互相倒数且不准把水到往三-CSDN博客

admin 11 2024-04-29 07:22:04

倒水问题 bfs (例:uva 10603)_有a、b、c三个杯子,容量分别为3升、7升和10升,三个杯子互相倒数且不准把水到往三-CSDN博客

  广度优先搜索(BFS)算法可以用来解决迷宫问题。在给定的迷宫中,起点和终点已知,障碍物和空地也已知。BFS算法可以找到从起点到终点的最短路径。下面是解决迷宫问题的Python代码,其中使用了BFS算法:

  ```python

  from collections import deque

  n, m = map(int,input().split())

  g = [list(map(int,input().split())) for i in range(n)]

  d = [(1,0),(-1,0),(0,1),(0,-1)]

  vis = [[0 for i in range(m)] for j in range(n)]

  x1, y1 , x2, y2 = map(int,input().split())

  q = deque()

  def bfs(x,y):

  q.append([x,y])

  vis[x][y] =1

  while q:

  now = q.popleft()

  nx = now[0]

  ny = now[1]

  if nx == x2-1 and ny == y2-1:

  break

  for i in d:

  dx = nx+i[0]

  dy = ny+i[1]

  if 0 <= dx < n and 0 <= dy < m:

  if vis[dx][dy] == 0 and g[dx][dy] == 1:

  q.append([dx,dy])

  vis[dx][dy] = vis[nx][ny] + 1

  return vis[x2-1][y2-1] - 1

  print(bfs(x1-1,y1-1))

  ```

  在这个代码中,我们首先输入了迷宫的大小和迷宫的地图。然后,我们定义了一个方向列表d,它包含了四个方向。接下来,我们定义了一个vis列表,用于记录每个位置是否被访问过。然后,我们输入了起点和终点的坐标,并定义了一个队列q。最后,我们定义了一个bfs函数,它使用BFS算法来搜索从起点到终点的最短路径,并返回路径长度。在主函数中,我们调用bfs函数并输出结果。

上一篇:俄罗斯真的很"记仇"|俄罗斯|英格兰|欧锦赛_新浪科技_新浪网
下一篇:体彩打开世界杯竞猜大门_国家体育总局
相关文章

 发表评论

暂时没有评论,来抢沙发吧~

返回顶部小火箭