Для решения данной задачи можно воспользоваться динамическим программированием. Ниже представлен код программы на Python, который находит путь с максимальной суммой монет:

def find_maximum_coins_path(N, M, coins):
dp = [[0 for _ in range(M)] for _ in range(N)]
for i in range(N):
for j in range(M):
if i == 0 and j == 0:
dp[i][j] = coins[i][j]
elif i == 0:
dp[i][j] = dp[i][j-1] + coins[i][j]
elif j == 0:
dp[i][j] = dp[i-1][j] + coins[i][j]
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + coins[i][j]
path = []
i, j = N-1, M-1
while i > 0 or j > 0:
path.append((i, j))
if i == 0:
j -= 1
elif j == 0:
i -= 1
elif dp[i-1][j] > dp[i][j-1]:
i -= 1
else:
j -= 1
path.append((0, 0))
path.reverse()
return dp[N-1][M-1], path
# Пример использования
N = 3
M = 4
coins = [
[1, 2, 3, 4],
[5, 6, 7, 8],
[9, 10, 11, 12]
]
max_coins, path = find_maximum_coins_path(N, M, coins)
print("Максимальное количество монет:", max_coins)
print("Путь с максимальным количеством монет:")
for i, j in path:
print(f"({i}, {j}) ->", end=" ")

Программа принимает на вход размеры поля N и M, а также двумерный массив coins, содержащий количество монет в каждой клетке поля. Далее программа использует динамическое программирование для нахождения пути с максимальной суммой монет и выводит этот путь, а также общее количество монет, которое удалось собрать кладоискателю.