|
Обледенение
(Время: 3 сек. Память: 32 Мб Сложность: 57%)
Представим лобовое стекло автомобиля в виде сетки из n строк и m столбцов. На пересечении строки i и столбца j стекло покрыто льдом толщиной ci,j.
Толщина 0 означает, что клетка не покрыта льдом и даёт беспрепятственный обзор, иначе клетка не даёт обзора вообще. Чтобы начать поездку, необходимо, чтобы хотя бы k клеток давали обзор.
У стекла имеется обогрев, который за одну секунду уменьшает толщину льда на 1 в каждой клетке. При этом, если образовался кусок льда, состоящий из нескольких клеток, который не касается рамки стекла, то он падает, тем самым исчезая со стекла. Заметим, что этот кусок пропадает моментально и никак не влияет на другие льдинки. Две клетки принадлежат одному куску льда, если они имеют общую сторону и их толщина больше 0. Кусок льда считается касающимся рамки стекла, если в нём есть клетка из крайней строки и/или из крайнего столбца.
Выясните сколько секунд нужно подождать с момента начала обогрева, чтобы можно было начинать поездку.
Входные данные
Первая строка входного файла INPUT.TXT содержит целые числа n, m и k – размеры стекла и необходимая видимость, соответственно (2 ≤ n, m ≤ 450; 1 ≤ k ≤ n×m).
В следующих n строках содержатся по m чисел ci,j, разделённых пробелом (1 ≤ ci,j ≤ 109).
Выходные данные
В выходной файл OUTPUT.TXT выведите количество секунд, через которое стекло будет обладать необходимой видимостью.
Примеры
№ | INPUT.TXT | OUTPUT.TXT |
1 | 5 5 9
9 9 9 9 9
9 2 1 3 9
9 1 9 2 9
9 4 5 1 9
9 9 9 9 9 | 5 |
2 | 3 3 6
9 8 7
4 5 6
3 2 1 | 6 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| |