Один из подходов к решению этого вопроса состоит в том, чтобы определить массив возможных мест для вора, который не будет захвачен для каждого шага 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])
Это означает, что вор не может быть в какой-либо пещере, предполагая, что его не поймали.