Giả sử chúng ta chơi trò chơi bị mắc kẹt trong mê cung. Mê cung được biểu diễn bằng ma trận n x m, mỗi ô chứa ký hiệu: 'O' (chặn), 'D' (lối thoát), 'S' (vị trí bắt đầu), '-' (đi được). Chúng ta có la bàn để tìm đường đến 'D', nhưng chỉ được dùng tối đa k lần. Cần xác định có thể thoát mê cung với ≤ k lần dùng la bàn không.
Thuật toán
Dùng DFS đệ quy với tham số: vị trí hiện tại, lưới, kích thước, k còn lại, từ điển predecessor (lưu ô cha).
Tại ô 'D': nếu k == 0 → True, ngược lại → False.
Tìm các ô lân cận hợp lệ (không phải 'O', không phải ô cha).
Nếu số ô lân cận > 1 → phải dùng la bàn (k - 1), else giữ nguyên k.
Đệ quy tiếp tục tìm kiếm.
Mã nguồn 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)
Đầu vào / Đầu ra
True