시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 1024 MB | 59 | 35 | 34 | 69.388% |
Юный программист решил придумать собственную игру. Игра происходит на поле размером N × N клеток, в некоторых клетках которого расположены города (каждый город занимает одну клетку; в каждой клетке может располагаться не более одного города). Всего должно быть чётное количество городов.
Изначально про каждую клетку игрового поля известно, расположен ли в ней город или нет. Чтобы начать игру, необходимо разделить игровое поле на два государства так, чтобы в каждом государстве было поровну клеток-городов.
Граница между государствами должна проходить по границам клеток таким образом, чтобы из любой клетки каждого государства существовал путь по клеткам этого же государства в любую другую его клетку (из клетки можно перейти в соседнюю, если они имеют общую сторону). Каждая клетка игрового поля должна принадлежать только одному из двух государств, при этом государства не обязаны состоять из одинакового количества клеток.
Требуется написать программу, которая с учетом сказанного разделит клетки заданного игрового поля между двумя государствами.
Первая строка входного файла содержит одно целое положительное число N, задающее размер игрового поля (1 ≤ N ≤ 50).
Последующие N строк содержат по N заглавных латинских букв (без пробелов), кодирующих соответствующие клетки игрового поля: ‘C’ обозначает клетку, занятую городом, ‘D’ – пустую клетку. Гарантируется, что на поле есть хотя бы два города и всего их четное число.
Выходной файл должен содержать N строк по N цифр (без пробелов) в каждой, кодирующих соответствующие клетки. Цифра 1 обозначает, что данная клетка принадлежит первому государству, цифра 2 – данная клетка принадлежит второму государству.
Если решений несколько, необходимо вывести любое из них.
3 DDD DDC DDC
222 212 211
5 DDDDD CDCDC DCCDC DDDDD DDDDD
11111 12221 12221 11111 11111