Задача №114858. Пранк в IKEA
Популярный видеоблогер Паша решил для увеличения численности своего канала снять какой-нибудь пранк. В качестве места для съемки Паша выбрал гипермаркет товаров для дома IKEA.
Один из залов в гипермаркете можно представить в виде клетчатого поля \(n \times m\). Некоторые клетки этого поля заняты диванами. На текущий момент все диваны находятся в сложенном состоянии и каждый диван занимает ровно две соседние по стороне клетки. Никакие два дивана не пересекаются, то есть каждая клетка занята не более чем одним диваном. Все остальные клетки поля, не занятые диванами, свободны.
Паша решил разложить как можно больше диванов, чтобы максимально затруднить проход через зал, после чего снять реакцию покупателей. В разложенном виде диван занимает квадрат \(2 \times 2\), который содержит две клетки, которые диван занимает в сложенном виде, а другие две клетки однозначно определяются направлением, в котором диван раскладывается.
Помогите Паше определить, какое максимальное количество диванов он может разложить, а также выведите инструкцию, показывающую, какие именно диваны для этого требуется разложить.
В первой строке даны два целых числа \(n\) и \(m\) — размеры поля (\(1 \le n, m \le 1\,000\)).
В следующих \(n\) строках дано по \(m\) символов — описание поля. Символ « . » соответствует пустой клетке. Клетки, занятые диванами, обозначаются строчными или заглавными английскими буквами. Две клетки одного дивана обозначаются одинаковым символом. Клетки диванов, касающихся по стороне, обозначаются разными символами. Если диван обозначается строчной буквой, он раскладывается вверх или влево, а если заглавной, то вниз или вправо.
В первой строке выведите целое число — максимальное количество диванов, которое Паша сможет разложить. В следующих \(n\) строках выведите по \(m\) символов — описание поля с разложенными диванами. Символ « . » соответствует пустой клетке. Клетки, занятые диванами, обозначаются цифрами. Клетки одного дивана должны обозначаться одной цифрой. Клетки соседних по стороне диванов должны обозначаться разными цифрами.
4 4 .AA. A..a A..a .aa.
2 .00. 1001 1221 .22.
3 4 .XX. .... YYZZ
1 .00. .00. 1122
3 4 .XX. .... yyzz
2 .00. 1122 1122