| Автор: | А. Кленин | Ограничение времени: | 1 сек | |
| Входной файл: | input.txt | Ограничение памяти: | 256 Мб | |
| Выходной файл: | output.txt | |||
| Максимальный балл: | 100 |
Приложение дополненной реальности пытается найти на изображении,
полученном с камеры телефона, метку, представляющую собой ярко раскрашенный прямоугольник.
Благодаря контрастному цвету прямоугольника на этапе предварительной обработки
изображение удалось преобразовать в массив из W на H элементов,
каждый из которых равен либо '#' (ASCII 35),
если он принадлежит прямоугольнику,
либо '.' (ASCII 46) в противном случае.
#' вместо '.' или наоборот.
В первом примере теста ошибочным может быть левый верхний элемент элемент непосредственно справа от него, элемент непосредственно снизу от него. Все остальные варианты из нуля или одной ошибки не дают прямоугольника в результате исправления.
Напишите программу, которая по данному изображению подсчитывает количество различных возможных положений метки.
Первая строка входного файла содержит целые числа W H N.
Следующие H строк содержат по W символов . и # каждая —
изображение после предварительной обработки.
Выходной файл должен содержать единственное целое число — количество возможных расположений метки.
1 ≤ W, H ≤ 100, 0 ≤ N ≤ W × H
Решения работающие для W, H ≤ 20 оцениваются из 50 баллов. Баллы выставляются за каждый успешно пройденный тест.
| № | Входной файл (input.txt) |
Выходной файл (output.txt) |
|---|---|---|
| 1 | |
|
| 2 | |
|
Прямоугольник, подходящий для того, чтобы быть меткой, должен обладать следующим свойством: количество точек внутри этого прямоугольника + количество решёток вне этого прямоугольника не должно превосходить N.
Так как W, H ≤ 100, можно перебрать все возможные прямоугольники
и с помощью префиксных сумм (. = 1, # = 0) (100 баллов)
или двойного цикла (50 баллов), посчитать количество точек внутри прямоугольника.
Это количество обозначим P. Пусть рассматриваемый
прямоугольник имеет координаты x1, y1 — левый верхний угол,
x2, y2 — правый нижний угол.
Тогда общее количество клеток, входящих в рассматриваемый прямоугольник,
S = (x2 − x1 + 1) * (y2 − y1 + 1).
Общее количество решёток на изображении обозначим как C. Тогда количество решёток вне выбранного прямоугольника равно K = C − (S − P). Следовательно, количество действий для исправления изображения равно K + P. Асимптотика решения с использованием префикс сумм O(W4), с использованием двойного цикла — O(W6).