ГлавнаяСборникиТурнирыРазделыФорумыУчастникиПечатьПомощьО системе

Турниры > Отборочный турнир сезона «Осень — 2020» > задача:


F. Макс и морской бой

Отборочный турнир сезона «Осень — 2020»

Старт: 31.окт.2020 в 14:00:00
Финиш: 08.ноя.2020 в 23:00:00
Турнир завершён!
• Турнирная таблица

Задачи турнира

• A. Макс и выбор операции
• B. Макс и сонник
• C. Макс и оригинальный никнейм
• D. Макс и выгодные инвестиции --- 2
• E. Макс и снежный ком
• F. Макс и морской бой
• G. Макс и элемент паззла
• H. Макс и фестиваль настольных игр
• I. Макс и жонглёры
• J. Макс и вставка букв

Обратная связь

Если у вас есть предложения или пожелания по работе Contester, посетите форум сайта www.contester.ru.

Лимит времени 2000/2000/2000/2000 мс. Лимит памяти 65536/65536/65536/65536 Кб.

Макс и морской бой
Макс и морской бой
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
64 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Напомним правила игры в «морской бой». Вначале каждый из двух игроков берёт клетчатый лист и очерчивает на нём два одинаковых поля, содержащих $$$N$$$ столбцов и $$$M$$$ строк, — одно для своих кораблей, а другое для кораблей противника. Столбцы каждого из полей помечаются слева направо первыми $$$N$$$ буквами латинского алфавита, а строки — сверху вниз первыми $$$M$$$ натуральными числами. Таким образом, каждая клетка имеет уникальные координаты: например, левый верхний угол обозначается как a1. Затем каждый из игроков втайне от другого рисует на своём поле набор кораблей — фигур, составленных из клеток, имеющих общую сторону. Форма, количество и правила размещения кораблей зависят от конкретных вариантов игры.

На этом подготовка завершается, и игроки начинают по очереди обстреливать поле противника. Один игрок называет другому координаты клетки, по которой он стреляет. Если в этой клетке нет кораблей, второй игрок отвечает «Мимо» и получает право хода. В противном случае второй игрок говорит «Попал» (или «Потопил», если противник уже расстрелял все остальные клетки корабля), а первый может стрелять ещё раз. Цель игры — первым потопить все корабли соперника.

$$$* * *$$$

Макс скачал на смартфон игру «морской бой». Спустя несколько партий он заметил, что компьютерный противник всегда обстреливает клетки игрока в одном и том же порядке, поэтому играть с ним довольно скучно.

После обновления в игре появился режим выживания. В нём требуется поставить на своём поле единственный четырёхпалубник (прямоугольник $$$1 \times 4$$$ или $$$4 \times 1$$$) таким образом, чтобы компьютер потопил его как можно позже. Однако и компьютер при этом меняет свою стратегию: он заведомо не стреляет по клеткам, в которых четырёхпалубник не может оказаться, а впервые попав по нему, всегда добивает его тремя следующими выстрелами.

Макс хочет продержаться в режиме выживания как можно дольше. Помогите ему правильно поставить корабль.

Входные данные

Первая строка содержит целые числа $$$N$$$ и $$$M$$$ ($$$4 \le N, M \le 26$$$) — соответственно количество столбцов и строк игрового поля.

Следующие $$$M \times N$$$ строк описывают порядок, в котором компьютерный противник обстреливает клетки. Каждая из этих строк содержит координаты одной из клеток поля. Все координаты уникальны.

Выходные данные

Выведите одно целое число — максимальное количество выстрелов, после которых размещённый некоторым образом на поле четырёхпалубник будет потоплен.

Примеры

Входные данные
5 4
a1
b1
c1
d1
e1
a2
b2
c2
d2
e2
a3
b3
c3
d3
e3
a4
b4
c4
d4
e4
Выходные данные
14
Входные данные
4 4
c4
d3
d4
c3
a1
a2
a3
a4
b4
b3
b2
b1
c1
d1
c2
d2
Выходные данные
8

Примечание

В первом примере целесообразно разместить четырёхпалубник в клетках b4, c4, d4, e4. Компьютер не будет стрелять по клеткам с2, d2, e2, c3, d3, e3, так как после обстрела предыдущих клеток ясно, что корабль в них оказаться не может.

Для отправки решений необходимо выполнить вход.

www.contester.ru