Морской бой Морской бой — это игра, в которой надо находить корабли противника, спрятанные на некотором поле. Корабли бывают разной формы, но в нашей задаче будут использоваться только «Г»-образные фигуры, состоящие из 4 клеток. При этом они могут быть повёрнуты в любую сторону. Ниже изображены все возможные повороты корабля: Один из таких кораблей расположен на поле 5 х 5. Вы можете выстрелить одновременно по нескольким клеткам поля. Ваша задача выстрелить так, чтобы точно попасть в какую-нибудь клетку корабля. Например, если бы поле имело размер 3 х 3, то можно было бы выстрелить по выделенным ниже клеткам: Но этот выстрел неправильный, потому что корабль мог располагаться на поле так, как показано ниже, и тогда бы в него не попал ни один из наших выстрелов. Ниже приведён пример ещё одного выстрела по полю 3 х 3: Этот выстрел правильный. В этом случае мы точно попадём в корабль, как бы он ни был расположен. Но такого же результата можно добиться и с помощью выстрела по 3 клеткам: Вам нужно отметить на поде 6 × 6 клетки для выстрела так, чтобы точно попасть в корабль. При этом чем меньше клеток У вас будет отмечено, тем больше баллов вы получите. Вам нужно отметить на поле 5 × 5 клетки для выстрела так, чтобы точно попасть в корабль. При этом чем меньше клеток у вас будет отмечено, тем больше баллов вы получите. Но если после выстрела по отмеченным вами полям спрятанный корабль может остаться целым, то вы получите 0 баллов.
Привет! Давай разберёмся в задаче.
Тебе нужно расставить выстрелы на поле 5×5 так, чтобы в любом случае попасть в корабль, который представляет собой «Г»-образную фигуру из 4 клеток. Цель — использовать как можно меньше клеток для выстрелов, чтобы гарантированно попасть в корабль.
На картинке справа видно, что для поля 3×3 выстрелы расположены так, чтобы покрыть все возможные положения корабля. Аналогично, нам нужно сделать для поля 5×5.
Начнём с анализа всех возможных позиций корабля на поле 5×5. У нас есть 4 основных ориентации «Г»-образной фигуры (вверх, вниз, влево, вправо). Задача сводится к тому, чтобы выбрать наименьшее количество клеток, которые пересекутся с всеми возможными ориентациями.
Вот как можно расставить выстрелы на поле 5×5:
- Представь поле 5×5 так, что в каждой четвёртой строке и колонке ты делаешь выстрел. Это гарантирует покрытие корабля, поскольку любое положение «Г»-образной фигуры будет задето.
Пример расстановки:
- Клетки, по которым нужно выстрелить: (2, 2), (2, 4), (4, 2), (4, 4)
Таким образом, используя 4 выстрела, ты покрываешь все возможные расположения корабля на поле.
Если что-то непонятно или нужно больше деталей, дай знать!
