Задача №111822. Лесопосадки
Часто при вырубке леса для строительства, например, дорог проводятся компенсационные лесопосадки - равное или большее число деревьев высаживается в другом месте. Однако посаженный таким образом лес отличается от самостоятельно выросшего~--- при компенсационной посадке деревья обычно сажают в узлах регулярной решетки, что изменяет влияние деревьев друг на друга.
Павел занимается математическим моделированием роста деревьев, высаженных в узлах прямоугольной решетки.
Будем считать, что в узлы решетки размером \(n\times m\) высажены деревья. Два дерева считаются соседними, если узлы, в которых они растут, являются соседними по вертикали или по горизонтали. У каждого дерева есть своя высота, равная некоторому целому числу метров.
Павел считает, что высота деревьев изменяется с годами по следующему закону:
- если у дерева есть хотя бы один сосед, высота которого ровно на один метр больше высоты самого дерева, то через год высота дерева увеличится ровно на один метр
- если у дерева нет такого соседа, его высота через год останется прежней.
При моделировании роста деревьев по этим правилам рост всех деревьев остановится в тот момент, когда соседних деревьев с разницей в росте, равной одному метру, не останется. Павел хочет выяснить, сколько лет пройдет до этого момента и какая высота будет в этот момент у каждого дерева.
Помогите ему, напишите программу, которая по заданным начальным высотам деревьев выяснит, через сколько лет рост всех деревьев остановится и какой будет высота каждого дерева в этот момент.
В первой строке входного файла находятся два целых числа \(n\) и \(m\) - размеры участка леса (\(1 \le n, m \le 100\)). Следующие \(n\) строк содержат по \(m\) натуральных чисел, каждое из которых задает высоту соответствующего дерева. Высота каждого дерева не превышает \(100\).
В первой строке выходного файла выведите \(t\) - число лет, которое пройдет до того момента, когда все деревья перестанут расти. После этого выведите \(n\) строк по \(m\) чисел - каждое число должно быть равно высоте соответствующего дерева через \(t\) лет.
3 4 1 1 1 2 1 5 5 1 3 1 1 1
9 3 3 3 3 3 5 5 3 3 3 3 3