| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 8 | 4 | 4 | 50.000% |
R2-D2 решает кроссворд, составленный специально для дроидов. В этом кроссворде в клеточки нужно писать не буквы, а цифры.
Кроссворд представляет из себя клетчатое поле $n \times m$. Некоторые клетки заблокированы, а все остальные --- свободные. Словом в кроссворде назовем максимальный по включению вертикальный или горизонтальный отрезок свободных клеток. Иными словами, слово --- это отрезок клеток одного столбца или строки, ограниченный с обоих сторон краем поля или заблокированными клетками.
Исходно, каждая свободная клетка кроссворда содержит какую-то цифру. Цель дроида --- поменять цифры таким образом, чтобы каждое слово в кроссворде являлось палиндромом. Палиндром --- это строка, читающаяся одинаково как слева-направо так и справа-налево. При этом, чем меньше суммарное изменение цифр в кроссворде по сравнению с исходными, тем лучше. Поэтому, требуется найти такое решение кроссворда, при котором сумма по всем свободным клеткам модулей разности исходной цифры и цифры в решении, была минимальна.
Помогите R2-D2 решить кроссворд так, чтобы суммарное изменение цифр было минимально. Несложно заметить, что всегда есть способ заполнить кроссворд так, чтобы все слова были палиндромами. Например, заполнить все свободные клетки одинаковыми цифрами. Поэтому, решение всегда существует.
В первой строке дано два целых числа $n$ и $m$ --- размеры поля (1ドル \le n, m \le 1,000円$).
В следующих $n$ строках дано по $m$ символов --- описание кроссворда. Символы могут быть равны <<.>> или цифрам. Символ <<.>> соответствует заблокированной клетке. А символ с цифрой $d$ соответствует свободной клетке, в которой исходно написана цифра $d$.
Выведите описание искомого решения кроссворда в том же формате, что и во входных данных. Если решений несколько, можете вывести любое.
3 3 123 456 789
323 454 323
4 3 .2. .05 .2. 10.
.1. .22 .2. 11.
10 10 .538...... ...4...4.. ...459157. 5...6..6.. 7.16304815 9...6..1.. 5...8..2.. 138631.351 2...3...7. 7.......4.
.535...... ...4...3.. ...531135. 5...3..1.. 2.11800811 1...6..1.. 5...8..3.. 136631.343 2...3...7. 5.......4.
В первом примере в кроссворде есть 6ドル$ слов, соответствующих каждому столбцу и строке поля. В оптимальном решении, суммарное изменение цифр равно 20ドル$.
Во втором примере, помимо слов длины 1ドル,ドル есть следующие слова: 2020, 05, 10. В оптимальном решении, суммарное изменение цифр равно 7ドル$.