Giả sử, chúng ta đang chơi một trò chơi mà chúng ta bị mắc kẹt trong một mê cung. Chúng ta phải tìm đường thoát ra khỏi mê cung. Mê cung có thể được trình bày dưới dạng ma trận x m, trong đó n là số hàng và m là số cột. Mỗi ô / phần tử của ma trận chứa bất kỳ ký hiệu nào trong số các ký hiệu 'O', 'D', 'S' hoặc '-'. 'O' có nghĩa là con đường bị chặn, 'D' là đường ra khỏi mê cung, 'S' là vị trí bắt đầu của chúng ta và '-' có nghĩa là chúng ta có thể di chuyển qua con đường. Chúng ta có thể di chuyển tự do qua bất kỳ ô nào được đánh dấu '-'. Bây giờ, chúng tôi cũng có một la bàn sử dụng để chúng tôi có thể tìm đường ra (ô 'D') từ mê cung. Khi chúng ta phải tìm phương hướng, chúng ta phải sử dụng la bàn. Nhưng, chúng ta có thể sử dụng la bàn nhiều nhất k lần. Cho mê cung dưới dạng ma trận và số lần chúng ta có thể sử dụng la bàn; chúng ta phải tìm xem liệu chúng ta có thể thoát ra khỏi mê cung khi chỉ sử dụng la bàn nhiều lần hay không. Nếu có thể, chúng tôi trả về True, nếu không, chúng tôi trả về False.
Vì vậy, nếu đầu vào giống như lưới =
| - | 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; thì đầu ra sẽ là True.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
Xác định một hàm path_search (). Điều này sẽ lấy curr_pos, grid, total_rows, total_cols, k, tiền nhiệm
-
x:=x giá trị của curr_pos
-
y:=giá trị y của curr_pos
-
nếu lưới [x, y] giống như "*" thì
-
nếu k giống 0 thì
-
trả về True
-
-
nếu không,
-
trả về Sai
-
-
nếu không,
-
cha mẹ:=người tiền nhiệm [curr_pos]
-
succ_pos:=một danh sách mới từ các giá trị trả về của succesor_positions (curr_pos, grid, total_rows, total_cols, cha)
-
use_compass:=True nếu kích thước succ_pos> 1
-
đối với mỗi vị trí trong succ_pos, hãy thực hiện
-
tiền nhiệm [vị trí]:=curr_pos
-
nếu use_compass khác 0 thì
-
path_search (vị trí, lưới, total_rows, total_cols, k - 1, tiền nhiệm)
-
- nếu không,
-
path_search (vị trí, lưới, total_rows, total_cols, k, tiền nhiệm)
-
-
-
-
-
-
Định nghĩa một hàm succesor_positions (). Điều này sẽ lấy curr_pos, grid, total_rows, total_cols, cha
-
x:=x giá trị của curr_pos
-
y:=giá trị y của curr_pos
-
succ_pos:=một danh sách mới
-
o nếu y> 0 thì
-
trái:=x, y - 1
-
chèn bên trái vào cuối succ_pos
-
-
nếu y
-
phải:=x, y + 1
-
chèn ngay vào cuối succ_pos
-
-
nếu x> 0, thì
-
lên:=x - 1, y
-
chèn lên ở cuối succ_pos
-
-
nếu x
-
xuống:=x + 1, y
-
chèn xuống ở cuối succ_pos
-
-
nếu đối với mọi vị trí trong succ_pos, lưới [vị trí [0], vị trí [1]] là
-
không giống với "X" và pos không giống với gốc, sau đó -
-
trả về các phần tử trong succ_pos thỏa mãn điều kiện
-
-
Bây giờ thực hiện như sau -
-
curr_pos:=một cặp trống mới
-
đối với mỗi chỉ mục i, hàng mục trong lưới, thực hiện
-
đối với mỗi chỉ mục j, phần tử mục trong hàng, thực hiện
-
nếu phần tử giống với 'M', thì
-
curr_pos:=một cặp mới chứa i, j
-
-
-
-
tiền nhiệm:=một bản đồ mới nơi curr_pos:=ban đầu không có giá trị
-
path_search (curr_pos, lưới, n, m, k, tiền nhiệm)
Mã nguồn (Python)
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
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
grid = [['-', 'O', '-', 'O', '-', '-', '-', '-', '-', '-', 'O'], ['-', 'O', 'D', '-', 'O', '-', 'O', 'O', 'O', '-', 'O'], ['-', 'O', 'O', '-', 'O', '-', 'O', 'S', '-', '-', '-'], ['-', '-', '-', '-', '-', '-', 'O', 'O', 'O', 'O', '-']] , 4, 11, 3
Đầu ra
True