Найдите максимальную координату y пути в сетке
Мне дана квадратная сетка
0 0 0 0 0 0
1 0 0 1 1 1
1 1 0 0 0 0
1 1 1 1 1 0
1 1 1 1 0 0
1 1 1 1 1 0
Я могу перемещаться по сетке, двигаясь только вверх, вниз, влево, вправо, но не по диагонали. Мне нужно найти максимальную координату y пути длиной не более 10 единиц. Координата y увеличивается по мере того, как мы движемся вниз по вертикали.
В этом примере это будет 6, так как мы можем добраться до нижнего правого края сетки.
- Мне также нужно знать путь, чтобы добраться туда.
- Если оптимальных путей несколько, я могу вывести любой из них.
- Я также могу начать и закончить в любом месте в верхнем ряду (в данном случае
0 0 0 0 0 0) - Я не могу идти на клетку, содержащую 1, я могу ходить только на клетки, содержащие 0.
Я прочитал эту сетку в 2d-список. Я попытался решить эту проблему с помощью модифицированного dfs, однако он зацикливается навсегда и не дает ответа.
def dfa(curr_X,curry,steps_taken,a,distance_from_start,path_taken=[0]):
if (not path_taken):
path_taken=[0]
if steps_taken>28:
return path_taken
else:
if a[curry+1][curr_X]!=1:
if (not path_taken):
path_taken=[0]
path_taken[0]=path_taken[0]+1
path_taken.append("01")
return dfa(curr_X,curry+1,steps_taken+1,a,distance_from_start+1,path_taken)
else:
if a[curry][curr_X+1]!=1 and a[curry][curr_X-1]!=1:
if (not path_taken):
path_taken=[0]
path_taken_right=path_taken.append("11")
path_taken_left=path_taken.append("10")
if (not path_taken):
path_taken=[0]
right_path=dfa(curr_X+1,curry,steps_taken+1,a,distance_from_start,path_taken_right)
if (not path_taken):
path_taken=[0]
left_path=dfa(curr_X-1,curry,steps_taken+1,a,distance_from_start,path_taken_left)
temp_max=max(right_path[0],left_path[0])
if (temp_max==right_path[0]):
return dfa(curr_X+1,curry,steps_taken+1,a,distance_from_start,path_taken_right)
else:
return dfa(curr_X-1,curry,steps_taken+1,a,distance_from_start,path_taken_left)
elif a[curry][curr_X+1]!=1:
path_taken.append("11")
return dfa(curr_X+1,curry,steps_taken+1,a,distance_from_start,path_taken)
elif a[curry][curr_X-1]!=1:
path_taken.append("10")
return dfa(curr_X+1,curry,steps_taken+1,a,distance_from_start,path_taken)
else:
path_taken.append("00")
path_taken[0]=path_taken[0]-1
return dfa(curr_X,curry-1,steps_taken+1,a,distance_from_start-1,path_taken)
else:
path_taken.append("00")
path_taken[0]=path_taken[0]-1
return dfa(curr_X,curry-1,steps_taken+1,airspace,distance_from_start-1,path_taken)
Пошаговое выполнение программы с помощью отладчика не дает мне окончательного ответа на вопрос, почему она вечно зацикливается. Извините за длинный код, я не могу его сократить, так как мне нужно охватить крайние случаи, когда оптимальный путь начинается внизу слева или внизу справа. Я уверен, что эта проблема требует некоторого поиска в глубину, однако, если для этого не требуется поиск в глубину, я открыт для поиска лучшего метода.
BFS также может быть вариантом.
Помимо отсутствия циклов, кажется, что эта программа не может вечно зацикливаться/запускаться без ошибок. Поскольку есть только рекурсия, программа должна в конечном итоге завершиться или достичь предела рекурсии Python (по умолчанию 1000). Вероятно, происходит экспоненциальное пространство поиска. DFS необходимо пройти по набору visited, чтобы он не исследовал узлы, которые были замечены ранее на том же пути.
@kcsquared, большое спасибо! Код Visual Studio не предупреждает меня о .append() и кажется, что он много раз посещает один и тот же квадрат.
Используйте BFS для каждой начальной точки, а затем просто сканируйте матрицу, чтобы найти наибольшую достижимую точку y.
@DollarAkshay, как мне это реализовать? Я не совсем уверен в реализации.
Ответы 1
Как предлагали другие, либо DFS, либо BFS решит вашу проблему. Состояния, очевидно, являются местоположениями в сетке, и мы будем отслеживать путь, пройденный с помощью кода Crack (вправо = 0, вниз = 1, влево = 2, вверх = 3), который является основным видом цепной код. Учитывая вашу сетку, начиная с позиции (0,0):
start_coord = (0,0)
grid = [[0, 0, 0, 0, 0, 0],
[1, 0, 0, 1, 1, 1],
[1, 1, 0, 0, 0, 0],
[1, 1, 1, 1, 1, 0],
[1, 1, 1, 1, 0, 0],
[1, 1, 1, 1, 1, 0]]
Поскольку мы хотим достичь дальних концов сетки как можно быстрее, я реализую DFS, то есть добавляю к deque справа и выталкиваю справа.
import collections
def find_path(grid, start_coord):
state_queue = collections.deque([]) # Pending states which have not been explored yet
visited = {start_coord}
state = [start_coord, []] # Starting state
# Keeping track of the max y reached and the path taken to get there
max_y_reached = start_coord[0] # coordinates are (y,x)
path = []
while max_y_reached < len(grid) - 1:
# Getting all possible neighboring states
state_right = [(state[0][0],state[0][1]+1), state[1] + [0]] if state[0][1]+1 < len(grid[state[0][0]]) else None
state_down = [(state[0][0]+1,state[0][1]), state[1] + [1]] if state[0][0]+1 < len(grid) else None
state_left = [(state[0][0],state[0][1]-1), state[1] + [2]] if state[0][1]-1 >= 0 else None
state_up = [(state[0][0]-1,state[0][1]), state[1] + [3]] if state[0][0]-1 >= 0 else None
# adding to the queue all the unvisited states, as well as to the visited to avoid returning to states
for next_state in [state_right, state_down, state_left, state_up]:
if next_state is not None:
if next_state[0] in visited or grid[next_state[0][0]][next_state[0][1]] == 1:
pass
else:
state_queue.append(next_state)
visited.add(next_state[0])
# popping next state from the queue and updating the path if needed
try:
state = state_queue.pop()
if state[0][0] > max_y_reached:
max_y_reached = state[0][0]
path = state[1]
except IndexError:
break
return max_y_reached, path
Наконец, при вызове функции вы получаете:
max_y_reached, path = find_path(grid, start_coord)
print(max_y_reached) # 5
print(path) # [0, 1, 0, 1, 0, 0, 0, 1, 1, 1]
Обратите внимание, что если по какому-то пути вы достигли последней строки (максимально возможная координата y), цикл while прервется посередине. Если последняя строка недоступна, DFS перебирает все возможные состояния, прежде чем выйти из цикла while.
У вас есть доступ к IDE или редактору кода/текста? Код в настоящее время трудно читаем, и большинство IDE могут предупреждать вас о таких строках, как
path_taken_left=path_taken.append("10"), которые, помимо того, что являются неиспользуемой переменной, также фиксируют возвращаемое значениеlist.append(), которое ничего не возвращает. Непоследовательные стили именования и отсутствие пробелов также ухудшают читабельность и отладку.