Решение задачи 497

Условие:

Ежик стоит в левой нижней клетке поля 8×8. А в какой-то другой клетке
пасется Лошадка. На поле стоит туман, ничего не видно, но ежику надо найти Лошадку. Лошадка каждую минуту переходит на соседнюю по стороне
клетку и громко говорит, куда она перешла (влево, вправо, вверх или вниз).
Ежик тоже может сделать шаг в одну из соседних по стороне или диагона-
ли клеток, как только услышит Лошадку. Ежик найдет Лошадку, если
окажется с ней на одной клетке. Что же делать Ежику?

Решение:

Предположим, что мы видим Лошадку. В таком случае поймать ее (оказаться в одной клетке) не очень сложно. Сначала можно встать с ней на одну горизонталь, а потом, оставаясь с ней постоянно на одной горизонтали, каждый ход приблажаться. У нас преимущество — мы можем ходить по диагонали.

Вернемся к условию задачи. Пронумеруем все клетки от 1 до 64 (мы стоим на 64-ой). Также мы будем запоминать все ходы Лошадки, т.е. то, что она говорит. Изначально она могла находиться в одной из 63-ех возможных клетках. Мы ней знаем в какой, будем перебирать все 63 варианта.

Предполагаем, что Лошадка изначально стоит в первой клетке. То есть теперь мы ее как будто видим. Начинаем ее ловить, если мы ее поймали, то задача решена. Если нет, значит Лошадка изначально была не в первой клетке. Пусть на поиск Лошадки мы потратили N шагов.

Предполагаем, что Лошадка изначально стоит во второй клетке. Мы знаем какие первые N шагов она сделала (мы все запоминали). Значит мы знаем, где она находится сейчас, если она изначально была во второй клетке. Начинаем ее ловить, если поймали, то задача решена. Если нет, то изначально Лошадка была не во второй клетке. Пусть на поиск Лошадки мы потратили еще M шагов.

Предполагаем, что Лошадка изначально стоит в третьей клетке. Мы знаем какие первые N+M шагов она сделала (мы все запоминали). Значит мы знаем, где она находится сейчас, если она изначально была в третьей клетке. Начинаем ее ловить, если поймали, то задача решена. Если нет, то изначально Лошадка была не в третьей клетке. И так далее.

Перебираем все 63 варианта один за одним. В какой-то момент мы найдем Лошадку.