4213. Города

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

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

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

Напишите программу, которая разделит клетки заданного игрового поля между двумя государствами.

Вход. Первая строка содержит размер игрового поля n (1 ≤ n ≤ 50).

Последующие n строк содержат по n заглавных латинских букв (без пробелов), кодирующих соответствующие клетки игрового поля: C обозначает клетку, занятую городом, D – пустую клетку. Гарантируется, что на поле есть хотя бы два города и всего их чётное число.

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

Если решений несколько, необходимо вывести любое из них.

Пример входа 1	Пример выхода 1
3 DDD DDC DDC	222 212 211
Пример входа 2	Пример выхода 2
5 DDDDD CDCDC DCCDC DDDDD DDDDD	11111 12221 12221 11111

РЕШЕНИЕ

логика

Анализ алгоритма

Вычислим количество городов cnt на игровом поле. Первые cnt / 2 городов относим к первому государству, остальные – ко второму. Пока все cnt / 2 городов не будут отнесены к первому государству, пустые клетки будем также относить к первому государству. При таком разделении обе области государств будут связными.

Пример

Реализация алгоритма

Входное игровое поле читаем в массив s. Результирующее поле строим в массиве res.

#define MAX 55

char s[MAX][MAX], res[MAX][MAX];

Читаем входные данные.

scanf("%d\n",&n);

for(i = 0; i < n; i++)

gets(s[i]);

В переменной cnt подсчитаем количество городов.

cnt = 0;

for(i = 0; i < n; i++)

for(j = 0; j < n; j++)

if (s[i][j] == 'C') cnt++;

Двигаемся по полю сверху вниз и слева направо. Первые cnt / 2 городов относим к первому государству, остальные – ко второму. Пока все cnt / 2 городов не будут отнесены к первому государству, пустые клетки будем также относить к первому государству.

cnt /= 2;

for(i = 0; i < n; i++)

for(j = 0; j < n; j++)

{

if (cnt > 0) res[i][j] = '1'; else res[i][j] = '2';

if (s[i][j] == 'C') cnt--;

}

Выводим разделенное игровое поле между двумя государствами.

for(i = 0; i < n; i++)

puts(res[i]);