Задача С. Покрытие
Задачу добавил: alef
Успешно сдано решений: 48
Время на тест 2 с, память 256 Мб
Отдел UUU ведущего НИИ занимается выращиванием специальной органической пленки, которая необходима для проведения экспериментов. Пленка выращивается на специальной сетке, состоящей из квадратов со стороной 1.
Процесс выращивания занимает достаточно долгое время, и хорошо стимулируется специальным освещением. Однако очень сложно добиться того, чтобы толщина пленки росла равномерно. Поэтому сотрудники отдела UUU поступают следующим образом: те квадратики, толщина пленки в которых достигла нужной величины, они накрывают специальным непрозрачным материалом.
В распоряжении сотрудников имеется неограниченное число квадратов непрозрачного материала размером K х K. Они обратились к Кеше с просьбой написать программу, которая помогла бы им закрыть все квадратики пленки, достигшие нужной толщины. При этом ни один из квадратиков, не достигший нужной толщины, не должен закрываться этим непрозрачным материалом.
Конструктивные особенности устройства, в котором выращивается пленка, таковы, что квадраты из непрозрачного материала не могут выходить за границы сетки. Также нельзя накладывать квадраты из непрозрачного материала друг на друга: пленка очень тонкая и не выдержит такого давления. Разрезать квадраты из непрозрачного материала также нельзя.
Ваша задача — определить, возможно ли это, а также сколько потребуется квадратов из непрозрачного материала, чтобы закрыть пленку описанным образом.
Формат входного файла input.txt
Первая строка — целые числа N, M, K (1 ≤ N, M ≤ 1000, K ≤ min(N, M)) — размеры сетки (в квадратиках) и сторона квадрата из непрозрачного материала.
В каждой из следующих N строк содержится по M чисел 0 и 1 через пробел, описывающих состояние органической пленки. 0 обозначает квадратик, имеющий достаточную толщину, 1 — недостаточную.
Формат выходного файла output.txt
Первая строка — слово YES, если это возможно, и NO, если невозможно
Вторая строка (если первая YES) содержит целое число — количество квадратов, которое потребуется.
Пример входного файла
4 4 2
1 1 1 1
1 0 0 1
1 0 0 1
1 1 1 1
Пример выходного файла
YES
1