Задача C. Города

Автор:Центральная предметно-методическая комиссия по информатике   Ограничение времени:2 сек
Входной файл:cities.in   Ограничение памяти:256 Мб
Выходной файл:cities.out  

Условие

Юный программист решил придумать собственную игру. Игра происходит на поле размером N×N клеток, в некоторых клетках которого расположены города (каждый город занимает одну клетку; в каждой клетке может располагаться не более одного города). Всего должно быть чётное количество городов.

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

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

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

Система оценивания

Правильные решения для тестов, в которых всего два города, будут оцениваться из 40 баллов.

Формат входного файла

Первая строка входного файла содержит одно целое положительное число N, задающее размер игрового поля. Последующие N строк содержат по N заглавных латинских букв (без пробелов), кодирующих соответствующие клетки игрового поля: 'C' обозначает клетку, занятую городом, 'D' — пустую клетку. Гарантируется, что на поле есть хотя бы два города и всего их четное число.

Формат выходного файла

Выходной файл должен содержать N строк по N цифр (без пробелов) в каждой, кодирующих соответствующие клетки. Цифра 1 обозначает, что данная клетка принадлежит первому государству, цифра 2 — данная клетка принадлежит второму государству. Если решений несколько, необходимо вывести любое из них.

Ограничения

1 ≤ N ≤ 50

Примеры тестов

Входной файл (cities.in) Выходной файл (cities.out)
1
3
DDD
DDC
DDC
111
111
112
2
5
DDDDD
CDCDC
DCCDC
DDDDD
DDDDD
11111
11111
12222
22222
22222

0.041s 0.012s 15