| Автор: | Центральная предметно-методическая комиссия по информатике | Ограничение времени: | 2 сек | |
| Входной файл: | cities.in | Ограничение памяти: | 256 Мб | |
| Выходной файл: | cities.out | |||
| Максимальный балл: | 100 |
Юный программист решил придумать собственную игру. Игра происходит на поле размером N×N клеток, в некоторых клетках которого расположены города (каждый город занимает одну клетку; в каждой клетке может располагаться не более одного города). Всего должно быть чётное количество городов.
Изначально про каждую клетку игрового поля известно, расположен ли в ней город или нет. Чтобы начать игру, необходимо разделить игровое поле на два государства так, чтобы в каждом государстве было поровну клеток-городов.
Граница между государствами должна проходить по границам клеток таким образом, чтобы из любой клетки каждого государства существовал путь по клеткам этого же государства в любую другую его клетку (из клетки можно перейти в соседнюю, если они имеют общую сторону). Каждая клетка игрового поля должна принадлежать только одному из двух государств, при этом государства не обязаны состоять из одинакового количества клеток.
Требуется написать программу, которая с учетом сказанного разделит клетки заданного игрового поля между двумя государствами.
Правильные решения для тестов, в которых всего два города, будут оцениваться из 40 баллов.
1 ≤ N ≤ 50
| № | Входной файл (cities.in) |
Выходной файл (cities.out) |
|---|---|---|
| 1 | |
|
| 2 | |
|