Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Курсы ККДП
Дистрибутивы
Статьи
Ссылки


 

Обледенение

(Время: 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.TXTOUTPUT.TXT
15 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
23 3 6
9 8 7
4 5 6
3 2 1
6

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!


 Язык программирования C++
 Решение олимпиадных задач
 Региональные олимпиады
 Книги Фёдора Меньшикова
 Тренировочные олимпиады
 Школьный этап
 Муниципальный этап
 Региональный этап
 Полуфинал ВКОШП
 Личное первенство СФУ
 2011 / 2012
 2012 / 2013
 2013 / 2014
 2014 / 2015
 2015 / 2016
 2016 / 2017
 2017 / 2018
 2018 / 2019
 2021 / 2022
 2022 / 2023
 A. Вы все уже победители
 B. Заработай себе металлолома
 C. Обледенение
 D. Дата сайнс
 E. Вирусные воспоминания
 F. Докраска забора
 G. Скатерть
 H. История одного анекдота
 I. Кружок
 J. JuryGPT

Красноярский краевой Дворец пионеров, (c)2006 - 2024, ИНН 246305493507, E-mail: admin@acmp.ru



Домен whatasoft.ru: купить в магазине доменных имен Рег.ру