Республиканская олимпиада по информатике 2017 год, Павлодар

Задача C. Саперы

Ограничение по времени:

2 секунды

Ограничение по памяти:

256 мегабайт

Два сапера должны обезвредить все мины в минном поле. Поле представляет собой таблицу $n \times m$ ($n$ строк и $m$ столбцов), и в каждой клетке этой таблицы находится не больше одной мины. Строки таблицы пронумерованы от $1$ до $n$ сверху вниз, столбцы пронумерованы от $1$ до $m$ слева направо. Саперы хотят разделить все поле на двоих максимально справедливым образом, так чтобы части были равными (при каком-то повороте они должны совпасть) и разница в количестве мин в частях была минимальной. Делить можно только по границам клеток и части должны быть связными, т.е. из каждой клетки одной части можно дойти до любой другой клетки этой же части передвигаясь только по соседним по стороне клеткам одной части. Вам надо написать программу, которая будет делить поле на две части для саперов максимально справедливым образом. Гарантируется, что $m$ четное число.

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

Первая строка входных данных содержит два целых числа $n$($1\le n \le 1000$) и $m(1 \le m \le 1000)$. В каждой из следующих $n$ строк следуют по $m$ символов — описание поля. Если символ равен «.», то текущая клетка пустая. Если символ равен «*», то в этой клетке находится мина.

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

Выведите $n$ строк по $m$ символов «1» или «2» обозначающее какому саперу достанется текущая клетка.

Система оценки

В данной задаче ровно 100 тестов. За каждый пройденный тест участник получает $1$ балл.

Пример:

Вход

5 8
**.....*
...*.*..
*..*....
*....*..
.......*

Ответ

11111111
22222211
22112211
22111111
22222222

( Batyrkhan Orynkul )