在 Python 中检查指南针使用次数是否足以走出迷宫的程序
假设我们正在玩一个游戏，我们被困在迷宫中。我们必须找到走出迷宫的路。迷宫可以表示为xm矩阵，其中n是行数，m是列数。矩阵的每个单元格/元素包含任何符号“O”、“D”、“S”或“-”。'O'表示路径被阻塞，'D'是迷宫的出路，'S'是我们的起始位置，'-'表示我们可以通过路径。我们可以在任何带有“-”标记的单元格中自由移动。现在，我们还有一个指南针，我们可以使用它找到迷宫的出口路径（“D”单元格）。当我们必须找到方向时，我们必须使用指南针。但是，我们最多可以使用指南针k次。将迷宫作为矩阵以及我们可以使用指南针的次数；我们必须弄清楚我们是否可以在使用指南针多次的情况下走出迷宫。如果可能，我们返回True，否则我们返回False。
所以，如果输入像grid=
n=4，m=11，k=3；那么输出将为True。
源代码(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