Я пытался найти алгоритм для следующей проблемы, но не смог получить полное решение.
В матрице размера (100,100) каждое значение может быть - 0 - Открыть, 1 - заблокирован, 2 - открыт золотой монетой ,
Нет.золотых монет в матрице может быть от 0 до 10.
A находится в начальной позиции (0,0), а B - в позиции (m, n) в матрице.
задача состоит в том, чтобы найти кратчайший путь, по которому A может собрать все золотые монеты и доставить их в B. A может переместиться на Север, Юг, Восток или Запад.
Ниже приведен код, который я пробовал (лабиринт - это матрица, B - позиция B) -
def democode(maze, B):
#with some initialization over here
while len(queue) != 0:
i,j=queue.pop(0)
result+=1
for m,n in getneighbors(i,j):
if (0<=m<rows) and (0<=n<cols):
if m == B[0] and n == B[1]:
break
if maze[m][n] != 1 and visited[m][n] == 0:
queue.append((m,n))
visited[m][n] = 1
return result
Это решение не учитывает проблему обеспечения того, чтобы A собирал все золотые монеты до достижения B. Нужны некоторые предложения по улучшению этого кода, чтобы охватить всесценарии.