Сложенная карта
Сад Фредди стал настолько большим, что ему стала необходима карта, в которой он отобразит какие овощи и в какой области посажены. Он заказал высококачественную карту от Международной картографической Компании. Так как карта имеет большой масштаб, она не помещается на одной странице, поэтому должна быть разделена на несколько прямоугольных частей.
Даже с фиксированным размером части (она определяется размером страницы) и масштабом карты, количество частей карты может по-прежнему отличаться в зависимости от размещения сетки. Вам следует найти минимальное количество частей карты, достаточных для покрытия всей области сада Фредди.
Два из многих вариантов расположения региона Техас:
Давайте взглянем на пример. Слева отображено 14 частей карты, покрывающих регион. Но если положение карты немного подвинуть, то тот же регион можно покрыть всего 10 частями, не меняя их размер и ориентацию.
Все части карты должны принадлежать прямоугольной сетке, параллельные x и y осям. То есть касаться они могут сторонами только полностью, и не могут вращаться.
Входные данные
Состоит из нескольких тестов. Первая строка каждого теста содержит четыре целых числа: A[r], A[c], T[r] и T[c]. A[r] и A[c] задают разрешение входного изображения в пикселях (1 ≤ A[x] ≤ 1000), T[r] и T[c] - размер одной части карты в пикселях (1 ≤ T[x] ≤ 100). Каждая из следующих A[r] строк содержит A[c] символов, каждый из которых либо "X" (пиксель соответствует части сада, который следует накрыть частью карты) или "." (пиксель вне сада, который накрывать не следует). Точки региона формируют одну связную область.
Выходные данные
Для каждого теста вывести в отдельной строке наименьшее количество частей карты, которыми можно накрыть все пиксели типа "X".