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)