Республиканская олимпиада по информатике 2017 года за 10 класс | Казахстанские олимпиады

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

Два сапера должны обезвредить все мины в минном поле. Поле представляет собой таблицу $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» обозначающее какому саперу достанется текущая клетка.

Примеры

Вход

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

Выход

11111111
22222211
22112211
22111111
22222222