牛牛现在在一个大小为n xm的网格中(用b代表牛牛的位置)，现在牛牛打算到达网格中的*点，但是网格有些单元格中有许多围墙使牛牛无法通过。庆幸的是，牛牛有3个**可以将墙炸毁以至于他可以通过此处，牛牛每一移动只能移动到没有围墙的单元格中且只能移动至相邻的格子中，每一移动只能移动一步，使用**时也算作移动一步。现在牛牛想知道他最少移动多少步才能到达*点; 输入描述：输入的第一行给出网格的大小n， m(1≤n,m≤20) 随后n行m列输入网格的信息； 网格中的墙使用w表示;可自由通过的单元格用'.'表示;‘*’表示牛牛的目的地 b表示牛牛的起点; 数据保证起点和目的地都只有一个。 输出描述： 输出最少移动多少步才能到达*点；若无法到达，输出-1 用python3写该代码

```python from collections import deque def bfs(n, m, grid): directions = [(0, 1), (0, -1), (1, 0), (-1, 0)] visited = [[False] * m for _ in range(n)] q = deque() for i in range(n): for j in range(m): if grid[i][j] == 'b': q.append((i, j, 0, 3)) visited[i][j] = True break else: continue break while q: x, y, steps, bombs = q.popleft() if grid[x][y] == '*': return steps for dx, dy in directions: new_x, new_y = x + dx, y + dy if 0 <= new_x < n and 0 <= new_y < m and not visited[new_x][new_y]: if grid[new_x][new_y] == '.': visited[new_x][new_y] = True q.append((new_x, new_y, steps + 1, bombs)) elif grid[new_x][new_y] == 'w' and bombs > 0: visited[new_x][new_y] = True q.append((new_x, new_y, steps + 1, bombs - 1)) return -1 n, m = map(int, input().split()) grid = [list(input()) for _ in range(n)] print(bfs(n, m, grid)) ``` [2024-09-03 20:22:47 | AI写代码神器 | 360点数解答]