用 Python 编写程序检查走出迷宫所需的指南针使用次数是否足够
假设我们正在玩一个被困在迷宫中的游戏。我们必须找到走出迷宫的路。迷宫可以表示为一个 x m 矩阵,其中 n 是行数,m 是列数。矩阵的每个单元格/元素包含任何符号"O"、"D"、"S"或"-"。"O"表示路径被阻塞,"D"是走出迷宫的路,"S"是我们的起始位置,"-"表示我们可以穿过路径。我们可以自由穿过任何标有"-"的单元格。现在,我们还有一个指南针,我们可以使用它找到迷宫的出口路径("D"单元)。当我们必须找到方向时,我们必须使用指南针。但是,我们最多可以使用指南针 k 次。给定迷宫作为矩阵,以及我们可以使用指南针的次数;我们必须找出我们是否可以只使用指南针那么多次就可以走出迷宫。如果可能,我们返回 True,否则我们返回 False。
因此,如果输入像网格 =
| - | O | - | O | - | - | - | - | - | - | O |
| - | O | D | - | O | - | O | O | O | - | O |
| - | O | O | - | O | - | O | O | O | - | O |
| - | O | O | - | O | - | O | S | - | - | - |
| - | - | - | - | - | - | O | O | O | O | - |
n = 4, m = 11, k = 3; 那么输出将为 True。
为了解决这个问题,我们将遵循以下步骤 −
定义一个函数 path_search() 。这将需要 curr_pos、grid、total_rows、total_cols、k、predecessor
x:= curr_pos 的 x 值
y:= curr_pos 的 y 值
如果 grid[x, y] 与 "*" 相同,则
如果 k 与 0 相同,则
返回 True
否则,
返回 False
否则,
parent :=前任[curr_pos]
succ_pos := 来自 succesor_positions(curr_pos, grid, total_rows, total_cols, parent) 返回值的新列表
use_compass := 如果 succ_pos 的大小 > 则为 True 1
对于 succ_pos 中的每个位置,执行
predecessor[position] := curr_pos
如果 use_compass 非零,则
path_search(position, grid, total_rows, total_cols, k - 1, predeadline)
- 否则,
path_search(position, grid, total_rows, total_cols,k, predeadline)
定义一个函数 succesor_positions() 。这将需要 curr_pos、grid、total_rows、total_cols、parent
x:= curr_pos 的 x 值
y:= curr_pos 的 y 值
succ_pos := 一个新列表
o 如果 y > 0,则
left := x, y - 1
在 succ_pos 末尾插入 left
如果 y < total_cols - 1,然后
right := x, y + 1
在 succ_pos 的末尾插入 right
如果 x > 0,然后
up := x - 1, y
在 succ_pos 的末尾插入 up
如果 x < total_rows - 1,则
down := x + 1, y
在 succ_pos 末尾插入 down
如果对于 succ_pos 中的每个位置,grid[position[0], pos[1]] 都是
与"X"不同并且 pos 与父元素不同,则 −
返回 succ_pos 中满足条件的元素
现在执行以下操作 −
curr_pos := 一个新的空对
对于每个索引 i,网格中的项目行,执行
对于每个索引 j,行中的项目元素,执行
如果元素与 'M' 相同,则
curr_pos := 一个包含 i 的新对, j
predecessor := 一个新的映射,其中 curr_pos := 最初为 Null
path_search(curr_pos, grid, n, m, k, predecessor)
Source Code (Python)
让我们看看下面的实现以便更好地理解 −
def path_search(curr_pos, grid, total_rows, total_cols, k, predecessor): x, y = curr_pos if grid[x][y] == "D": if k == 0: print('True') else: print('False') else: parent = predecessor[curr_pos] succ_pos = list(succesor_positions(curr_pos, grid, total_rows, total_cols, parent)) use_compass = len(succ_pos) > 1 for position in succ_pos: predecessor[position] = curr_pos if use_compass: path_search(position, grid, total_rows, total_cols, k - 1, predecessor) else: path_search(position, grid, total_rows, total_cols, k, predecessor) def succesor_positions(curr_pos, grid, total_rows, total_cols, pred): x, y = curr_pos succ_pos = [] if y > 0: left = (x, y - 1) succ_pos.append(left) if y < total_cols - 1: right = (x, y + 1) succ_pos.append(right) if x > 0: up = (x - 1, y) succ_pos.append(up) if x < total_rows - 1: down = (x + 1, y) succ_pos.append(down) return filter(lambda pos: grid[pos[0]][pos[1]] != "O" and pos != pred, succ_pos) def solve(grid, n, m, k): curr_pos = () for i, row in enumerate(grid): for j, element in enumerate(row): if element == 'S': curr_pos = (i, j) path_search(curr_pos, grid, n, m, k, predecessor = {curr_pos: None}) grid = [['-', 'O', '-', 'O', '-', '-', '-', '-', '-', '-', 'O'], ['-', 'O', 'D', '-', 'O', '-', 'O', 'O', 'O', '-', 'O'], ['-', 'O', 'O', '-', 'O', '-', 'O', 'S', '-', '-', '-'], ['-', '-', '-', '-', '-', '-', 'O', 'O', 'O', 'O', '-']] solve(grid, 4, 11, 3)输入
grid = [['-', 'O', '-', 'O', '-', '-', '-', '-', '-', '-', 'O'], ['-', 'O', 'D', '-', 'O', '-', 'O', 'O', 'O', '-', 'O'], ['-', 'O', 'O', '-', 'O', '-', 'O', 'S', '-', '-', '-'], ['-', '-', '-', '-', '-', '-', 'O', 'O', 'O', 'O', '-']] , 4, 11, 3
输出
True
相关文章
有用资源
python 参考教程 - 该教程包含有关 python 的更多信息:https://www.cainiaomax.com/python/

