20. Поиск клада. Клад зарыт в одной из 16 клеток поля 4×4. Ты можешь копать в любой клетке, а тебе говорят «горячо» (клад в соседней клетке) или «холодно» (дальше). Придумай алгоритм, как найти клад за минимальное число попыток.

Нельзя определить гарантированное минимальное число попыток без уточнения правил подсказки: не сказано, считается ли соседней клетка только с общей стороной или также по диагонали, и относится ли «горячо» к клетке, выкопанной сейчас, или к предыдущей попытке. Кроме того, число попыток зависит от положения клада и от того, можно ли повторно копать в уже проверенной клетке.

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