Задача №111489. Города
Юный программист решил придумать собственную игру. Игра происходит на поле размером \(N \times N\) клеток, в некоторых клетках которого расположены города (каждый город занимает одну клетку; в каждой клетке может располагаться не более одного города). Всего должно быть чётное количество городов.
Изначально про каждую клетку игрового поля известно, расположен ли в ней город или нет. Чтобы начать игру, необходимо разделить игровое поле на два государства так, чтобы в каждом государстве было поровну клеток-городов.
Граница между государствами должна проходить по границам клеток таким образом, чтобы из любой клетки каждого государства существовал путь по клеткам этого же государства в любую другую его клетку (из клетки можно перейти в соседнюю, если они имеют общую сторону). Каждая клетка игрового поля должна принадлежать только одному из двух государств, при этом государства не обязаны состоять из одинакового количества клеток.
Требуется написать программу, которая с учетом сказанного разделит клетки заданного игрового поля между двумя государствами.
Первая строка входного файла содержит одно целое положительное число N, задающее размер игрового поля (\(1 \leq N \leq 50\)).
Последующие N строк содержат по \(N\) заглавных латинских букв (без пробелов), кодирующих соответствующие клетки игрового поля: ‘C’ обозначает клетку, занятую городом, ‘D’ – пустую клетку. Гарантируется, что на поле есть хотя бы два города и всего их четное число.
Выходной файл должен содержать \(N\) строк по \(N\) цифр (без пробелов) в каждой, кодирующих соответствующие клетки. Цифра 1 обозначает, что данная клетка принадлежит первому государству, цифра 2 – данная клетка принадлежит второму государству. Если решений несколько, необходимо вывести любое из них.
Правильные решения для тестов, в которых всего два города, будут оцениваться из 40 баллов.
Несмотря на выделение отдельной группы тестов с двумя городами, на окончательную проверку будут приниматься только решения, правильно работающие также для всех тестов из условия задачи.
3 DDD DDC DDC
111 111 112
5 DDDDD CDCDC DCCDC DDDDD DDDDD
11111 11111 12222 22222 22222