Как решить Задание Морской бой ВСОШ информатика 5, 6, 7, 8 Кл 24.10.24?
Задание 3. Морской бой
Морской бой это игра, в которой надо находить корабли противника, спрятанные на некотором поле. Корабли бывают разной формы, но в нашей задаче будут использоваться только «Г»‑образные фигуры, состоящие из 4 клеток. При этом они могут быть повёрнуты в любую сторону. Ниже изображены все возможные повороты корабля:
Один из таких кораблей расположен на поле 7×7. Вы можете выстрелить одновременно по нескольким клеткам поля. Ваша задача выстрелить так, чтобы точно попасть в какую‑нибудь клетку корабля. Например, если бы поле имело размер 3×3, то можно было бы выстрелить по выделенным ниже клеткам:
Но этот выстрел неправильный, потому что корабль мог располагаться на поле так, как показано ниже, и тогда бы в него не попал ни один из наших выстрелов.
Ниже приведён пример ещё одного выстрела по полю 3×3:
Этот выстрел правильный. В этом случае мы точно попадём в корабль, как бы он ни был расположен. Но такого же результата можно добиться и с помощью выстрела по 3 клеткам:
Вам нужно отметить на поле 7×7 клетки для выстрела так, чтобы точно попасть в корабль. При этом чем меньше клеток у вас будет отмечено, тем больше баллов вы получите. Но если после выстрела по отмеченным вами полям спрятанный корабль может остаться целым, то вы получите 0 баллов.
Ответы (3)
Чтобы попасть в «Г»‑образный корабль в виде сапожка (три в рид и один квадратик по краю сбоку) независимо от положения этого корабля придётся сделать не более 17 выстрелов:
По большой диагонали 7 выстрелов:
(1;1) ; (2;2) ; (3;3) (4;4) ; (5;5) ; (6;6) ; (7;7)
По двум малым диагоналям, длиной в три клетки:
(5;1) ; (6;2) ; (7;3)
(1;5) ; (2;6) ; (3;7)
и затем ещё 4 выстрела
(2;4) ; (4;2) ; (4;6) ; (6;4)
Итого получается 7+2*3+4=17 выстрелов.
1 2 3 4 5 6 7
- * 0 0 0 * 0 0
- 0 * 0 * 0 * 0
- 0 0 * 0 0 0 *
- 0 * 0 * 0 * 0
- * 0 0 0 * 0 0
- 0 * 0 * 0 * 0
- 0 0 * 0 0 0 *
На пустых клетках поля не получится разместить, указанные в условии задачи корабли.
Взгляните на следующую схему:
Здесь закрашены 16 клеток. И на оставшихся незакрашенными клетках не получится разместить ни один четырёхклеточный корабль Г-образной формы. То есть достаточно произвести 16 выстрелов.
По условию задания под названием "Морской бой" нужно на поле 7 на 7 гарантированно подбить все корабли. Выражаясь терминологией морского боя все корабли противника четырёхпалубные, Г-образной формы. Нужно сделать минимальное количество выстрелов, чтобы ни одного корабля не осталось. Таких выстрелов получилось 17. Вот они все на рисунке.
ВКонтакте