Воры в пещерах, кодирующих пазл

1

algorithm,puzzle,

алгоритм, головоломка,

Ответов: 1


1 принят

Один из подходов к решению этого вопроса состоит в том, чтобы определить массив возможных мест для вора, который не будет захвачен для каждого шага i, следующим образом:

thief[k-1][i-1] || thief[k-1][i+1]

Интуиция:
На шаге kвор не может быть (не пойман) в пещере, которую обыскивают (это O(n*m)часть).
Кроме того, он не может быть в пещере i, если для него было бы невозможно быть в любой соседней пещере в предыдущем раунде (что является второй частью n).

Это можно решить с помощью динамического программирования во mвремени, где nуказано количество пещер и mдлина предоставленного списка.

Когда вы закончите вычисление таблицы, ответ будет в основном:

NOT(thief[m][0] || thief[m][1] || ... || thief[m][n-1])

Это означает, что вор не может быть в какой-либо пещере, предполагая, что его не поймали.

алгоритм, головоломка,
Похожие вопросы