Морской бой — это игра, в которой надо находить корабли противника, спрятанные на некотором поле. Корабли бывают разной формы, но в нашей задаче будут использоваться только «Г»‑образные фигуры, состоящие из 4 клеток. При этом они могут быть повёрнуты в любую сторону. Ниже изображены все возможные повороты корабля: Один из таких кораблей расположен на поле 5×5 . Вы можете выстрелить одновременно по нескольким клеткам поля. Ваша задача выстрелить так, чтобы точно попасть в какую‑нибудь клетку корабля. Например, если бы поле имело размер 3×3 , то можно было бы выстрелить по выделенным ниже клеткам: Но этот выстрел неправильный, потому что корабль мог располагаться на поле так, как показано ниже, и тогда бы в него не попал ни один из наших выстрелов. Ниже приведён пример ещё одного выстрела по полю 3×3 : Этот выстрел правильный. В этом случае мы точно попадём в корабль, как бы он ни был расположен. Но такого же результата можно добиться и с помощью выстрела по 3 клеткам: Вам нужно отметить на поле 5×5 клетки для выстрела так, чтобы точно попасть в корабль. При этом чем меньше клеток у вас будет отмечено, тем больше баллов вы получите. Но если после выстрела по отмеченным вами полям спрятанный корабль может остаться целым, то вы получите 0 баллов.

В игре "Морской бой" задача состоит в том, чтобы стрелять по клеткам, в которые точно попадет "Г"-образный корабль, состоящий из 4 клеток. Давайте разберем, как можно разместить выстрелы на поле 5×5, чтобы гарантированно попасть в корабль, независимо от его ориентации.

Корабль "Г"-образной формы можно расположить на поле в различных ориентациях. Всего есть 8 уникальных ориентировок для такого корабля:

1. Прямые позиции:

   • Вверх
   • Вправо
   • Вниз
   • Влево

2. Повороты:

   • Вправо верхними клетками, т.е. "Г" идет вправо и вниз.
   • Вправо нижними клетками, т.е. "Г" идет вниз и вправо.
   • Влево верхними клетками, т.е. "Г" идет влево и вниз.
   • Влево нижними клетками, т.е. "Г" идет вниз и влево.

Теперь давайте определим минимальные клетки для стрельбы, чтобы гарантированно попасть в любой из этих вариантов. Учитывая, что поле 5×5, можно воспользоваться следующими стратегиями:

Выстрелы:

1. Соты: Отметить клетки, расположенные по диагонали, например:

   • (2,2), (2,3), (3,2), (3,3) — достаточно для попадания во все варианты "Г".

2. Крест: Также можно использовать:

   • (1,2), (2,1), (2,3), (3,2) — 4 клетки с такой конфигурацией не оставят шансов для укрытия корабля.

Обратите внимание, что стрелять не более чем по 4 клеткам, но диапазон эффективности также зависит от расположения корабля. Каждая из приведенных конфигураций гарантирует попадание в любую из позиций "Г"-образного корабля.

Таким образом, оптимальная стратегия заключается в том, чтобы выделить от 4 до 5 клеток, правильно организованных, для гарантированного попадания. Эффективность выстрелов можно оценить по тому, сколько уникальных позиций корабля они могут перекрыть, и чем меньше клеток будет использовано для этого, тем выше будет ваша оценка.

Надеюсь, это поможет вам с вашей задачей на экзамене!