Задача B. Распознавание метки

Автор:А. Кленин   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  
Максимальный балл:100  

Условие

Приложение дополненной реальности пытается найти на изображении, полученном с камеры телефона, метку, представляющую собой ярко раскрашенный прямоугольник. Благодаря контрастному цвету прямоугольника на этапе предварительной обработки изображение удалось преобразовать в массив из W на H элементов, каждый из которых равен либо '#' (ASCII 35), если он принадлежит прямоугольнику, либо '.' (ASCII 46) в противном случае.

Алгоритм предварительной обработки неидеален, и мог совершить от 0 до N ошибок — выдать '#' вместо '.' или наоборот.

В первом примере теста ошибочным может быть левый верхний элемент элемент непосредственно справа от него, элемент непосредственно снизу от него. Все остальные варианты из нуля или одной ошибки не дают прямоугольника в результате исправления.

Напишите программу, которая по данному изображению подсчитывает количество различных возможных положений метки.

Формат входного файла

Первая строка входного файла содержит целые числа W H N. Следующие H строк содержат по W символов . и # каждая — изображение после предварительной обработки.

Формат выходного файла

Выходной файл должен содержать единственное целое число — количество возможных расположений метки.

Ограничения

1 ≤ W, H ≤ 100, 0 ≤ N ≤ W × H

Описание системы оценивания

Решения работающие для W, H ≤ 20 оцениваются из 50 баллов. Баллы выставляются за каждый успешно пройденный тест.

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
3 3 1
.#.
##.
...
3
2
2 2 0
#.
.#
0

Разбор

Прямоугольник, подходящий для того, чтобы быть меткой, должен обладать следующим свойством: количество точек внутри этого прямоугольника + количество решёток вне этого прямоугольника не должно превосходить N.

Так как W, H ≤ 100, можно перебрать все возможные прямоугольники и с помощью префиксных сумм (. = 1, # = 0) (100 баллов) или двойного цикла (50 баллов), посчитать количество точек внутри прямоугольника. Это количество обозначим P. Пусть рассматриваемый прямоугольник имеет координаты x 1, y 1  — левый верхний угол, x 2, y 2  — правый нижний угол. Тогда общее количество клеток, входящих в рассматриваемый прямоугольник, S = (x 2 − x 1 + 1) * (y 2 − y 1 + 1).

Общее количество решёток на изображении обозначим как C. Тогда количество решёток вне выбранного прямоугольника равно K = C − (S − P). Следовательно, количество действий для исправления изображения равно K + P. Асимптотика решения с использованием префикс сумм O(W4), с использованием двойного цикла — O(W6).


0.116s 0.021s 13