Морской бой

Это дополнительный листок.

Этот листок посвящен игре в морской бой. Программы в этом листке получают на вход поле для игры в морской бой. Поле задается следующим образом. Сначала указано количество строк в поле n, затем указано количество столбцов в поле m. Далее идет n строк по m символов в каждой строке. Каждый символ строки может быть либо точкой (.), либо диезом (#). Точка означает, что данная клетка пустая, диез означает, что данная клетка занята.

Пример задания поля:

4 6
###.#.
....#.
.#..#.
.#..#.

На этом поле три корабля - один вертикально размещенный 4-клеточный, второй горизонтально размещенный трехклеточный, третий вертикально размещенный двухклеточный.

Два корабля не могут соприкасаться по вертикали, горизонтали или диагонали.

В разных задачах корабли могут быть различными. В задачах A-E корабли являются отрезками прямых, лежащих на одной горизонтали или одной вертикали, в задачах F-J - прямоугольниками, в задачах K-O — произвольными связными фигурами.

Файловый ввод-вывод

Поскольку в задачах этого листка при отладке программы придется много раз запускать ее на одинаковых полях, то для упрощения процесса ввода данных можно сохранить пример карты в текстовом файле.

Программа может использовать либо стандартный ввод-вывод (чтение данных со стандартного ввода при помощи функции input, вывод результата на стандартный вывод при помощи функции print), либо читать данные из файла input.txt и выводить результат в файл output.txt. Файловому вводу-выводу будет посвящен один из следующих листочков, пока можно про файловый ввод-вывод прочитать здесь.

Подсказки для реализации

Перебор соседних клеток

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

Moves4 = [[1, 0], [0, 1], [-1, 0], [0, -1]]

Тогда если текущая клетка имеет координаты x, y, то перебрать все соседние с ней клетки можно так:

for dx, dy in Moves4:
    nx, ny = x + dx, y + dy
    # Обработка клетки nx, ny

Каемочка

При проверки соседних клеток возможна ситуация выхода за границы поля, если текущая клетка находится на краю поля. Вместо проверок условия выхода за границы поля, удобно добавить к полю “ каемочку” из дополнительных клеток (добавить строки снизу и сверху поля и столбцы слева и справа).

A: Количество кораблей

Определите количество кораблей на поле.

Ввод	Вывод
4 6 ###.#. ....#. .#..#. .#..#.	3

Подсказка. Нужно считать количество верхних (левых) концов кораблей. Как определить, является ли клетка верхним (левым) концом?

B: Самый большой корабль

Определите количество клеток в самом большом корабле.

Ввод	Вывод
4 6 ###.#. ....#. .#..#. .#..#.	4

Подсказка. Найдя верхний (левый) конец корабля нужно посчитать, сколько в нем клеток.

С: Корректность карты

Дана карта. Проверьте, является ли размещение кораблей на ней корректным. Выведите YES или NO.

Ввод	Вывод
4 6 ###.#. ....#. .#..#. .#..#.	YES
4 6 .##... .#.... .#.... ......	NO
4 6 ..##.. .#.... .#.... ......	NO

Подсказка. Карта является корректной, если каждая занятая кораблем клетка не имеет диагональных соседних занятых клеток, а также не имеет одновременно соседей по горизонтали или по вертикали.

D: Меткий выстрел

Дана карта и дана клетка на поле. Клетка задана в виде двух чисел - номера строки i и номера столбца j. Строки нумеруются сверху вниз от 1, столбцы нумеруются слева направо от 1.
Игрок выстрелил в эту клетку, после чего потопил весь тот корабль, в который попал выстрел (а если не попал, то ничего не потопил). Выведите получившуюся карту.
При выводе поля не нужно выводить его размеры, только изображение самого поля.

Ввод	Вывод
4 6 ###.#. ....#. .#..#. .#..#. 3 2	###.#. ....#. ....#. ....#.

Е: Свободное место

Задана карта. Определите максимальный размер корабля, который можно установить на эту карту не нарушая правила игры.

Ввод	Вывод
4 6 ###.#. ....#. #..... #.....	4

Подсказка. Сначала попробуйте найти место для вертикального корабля, затем - для горизонтального. Для поиска места находим свободную клетку, в которую можно разместить корабль, затем начинаем достаивать корабль от этой клетки пока это возможно. Если стало невозможно - обрываем корабль и идем дальше по строке, затем переходим к следующей строке и т.д.

F: Количество кораблей-2

Теперь все корабли могут быть произвольными прямоугольниками, опять-таки не соприкасающимися. Определите количество кораблей на поле.

Ввод	Вывод
4 6 ###..# ...... .###.# .###..	4

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

G: Самый большой корабль-2

Определите количество клеток в самом большом корабле.

Ввод	Вывод
4 6 ###..# ...... .###.# .###..	6

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

H: Меткий выстрел-2

Ввод	Вывод
4 6 ###.#. ....#. ##..#. ##..#. 3 2	4 6 ###.#. ....#. ....#. ....#.

I: Корректность карты-2

Дана карта. Проверьте, является ли размещение кораблей на ней корректным. Выведите YES или NO.

Ввод	Вывод
4 6 ###..# ...... ##..#. ##..#.	YES
4 6 .###.. .#.#.. .###.. ......	NO
4 6 ..##.. .#.... .#.... ......	NO

Подсказка. Нужно обнаруживать и выделять все корабли. Обнаружив корабль, можно проверить, что он прямоугольный и не касается других кораблей. При этом сам корабль можно сразу же стирать с поля.

J: Свободное место-2

Задана карта. Определите максимальный размер корабля (в клетках), который можно установить на эту карту не нарушая правила игры.
В этой задаче ограничения на n и m будут уменьшены.

Ввод	Вывод
4 6 ###.#. ...... #..... #.....	8

Подсказка. Переберем все возможные размещения нового корабля.

K: Меткий выстрел-3

Теперь все корабли могут быть произвольными связными множествами клеток (связность определяется по общим сторонам клеток), опять-таки не соприкасающимися. Также возможна ситуация, когда один корабль целиком находится внутри другого корабля, но при этом они не соприкасаются ни сторонами, ни углами.
Дана карта и дана клетка на поле. Игрок выстрелил в эту клетку, после чего потопил весь тот корабль, в который попал выстрел (а если не попал, то ничего не потопил). Выведите получившуюся карту.

Ввод	Вывод
6 6 .##### #....# #.##.# #.#..# #....# ###### 3 3	.##### #....# #....# #....# #....# ######

Подсказка. Нужно научиться выделять каждый отдельный корабль при помощи волнового алгоритма.

L: Количество кораблей-3

Дана карта. Определите количество кораблей на этой карте.

Ввод	Вывод
6 6 .##### #....# #.##.# #.#..# #....# ######	2

Подсказка. Будем по очереди находить и стирать корабли, считая их число.

M: Самый большой корабль-3

Определите количество клеток в самом большом корабле.

Ввод	Вывод
6 6 .##### #....# #.##.# #.#..# #....# ######	19

Подсказка. Модифицируем волновой алгоритм так, чтобы он возвращал количество клеток в обнаруженном корабле.

N: Корректность карты-3

Дана карта. Проверьте, является ли размещение кораблей на ней корректным. Выведите YES или NO.

Ввод	Вывод
6 6 .##### #....# #.##.# #.#..# #....# ######	YES
6 6 .##### ##...# #.##.# #.#..# #....# ######	NO

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

O: Свободное место-3

Дана карта. Определите максимальный размер корабля (в клетках), который можно установить на эту карту не нарушая правила игры.

Ввод	Вывод
4 6 ###.#. ....#. #..... #.....	5

Подсказка. Допустим, мы нашли свободную клетку. Запустим волновой алгоритм для строительства нового корабля из этой клетки. Проделаем эту операцию со всеми клетками.