Морской бой

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

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

На этом поле три корабля - один вертикально размещенный 4-клеточный, второй горизонтально размещенный трехклеточный, третий вертикально размещенный двухклеточный.
Два корабля не могут соприкасаться по вертикали, горизонтали или диагонали.
Размеры поля могут быть произвольными от 1 до 1000. Для хранения поля удобно сделать глобальный массив int Map[1002][1002]. Элементы этого массива будут равны 0, если клетка - пустая или 1 - если клетка занята. Все остальные функции будут работать с этим массивов. Мы создадим массив максимального размера, добавив еще 2 строки и два столбца для хранения каемочки, ограничивающей наше поле. Эту каемочку нужно заполнить нулями - для удобства использования во всех алгоритмах.
Кроме того, заведем две глобальные переменные n и m для хранения размеров поля. Итак, начало каждой программы будет таким:

int n, m;
int Map[1002][1002];

Сами элементы поля будут храниться в элементах массива


Map[i][j]

, где 1≤i≤n и 1≤j≤m.
Программа обязательно должна содержать функцию ReadMap(), считывающую данные и записывающую их в массив Map и функцию, решающую основную задачу. При этом функция main() должна иметь вид вроде:

int main()
{
    ReadMap();
    cout<<CountShips()<<endl;
}

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

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

Во всех задачах этого листка входные данные для программы записаны в файле input.txt, а результат работы программы должен быть сохранен в файле output.txt.
Поэтому нужно научиться работать с файлами. Файловый ввод-вывод ничем не отличается от консольного. За единственным исключением – если данные читаются из файла, то в любой момент можно вернуться к началу файла и считать все заново.

Для того, чтобы в C++ работать с файлами необходимо подключить заголовочный файл fstream:

     #include <fstream>

После этого можно объявлять объекты, привязанные к файлам: для чтения данных из файла используются объекты типа ifstream (аббревиатура от input file stream, для записи данных в файл используются объекты типа ofstream (output file stream). Например

     ifstream fin;  // Поток fin будем использовать для чтения данных
     ofstream fout; // Поток fout будем использовать для вывода данных

Чтобы привязать тот или иной поток к файлу (открыть файл для чтения или для записи) используется метод open, которому необходимо передать параметр – текстовую строку, содержащую имя открываемого файла.

     fin.open("input.txt");
     fout.open("output.txt");

После открытия файлов и привязки их к файловым потокам, работать с файлами можно так же, как со стандартными потоками ввода-вывода cin и cout. Например, чтобы вывести значение переменной x в поток fout используются следующая операция

     fout<<x;

А чтобы считать значение переменной из потока fin

     fin>>x;

Для закрытия ранее открытого файла используется метод close() без аргументов:

     in.close();
     out.close();

Закрытый файловый поток можно переоткрыть заново при помощи метода open, привязав его к тому же или другому файлу.

0: Разминка

В файле input.txt записаны два целых числа. Выведите в файл output.txt их сумму.

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

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