764. Дом

Петр приватизировал участок размером m квадратов с севера на юг и n квадратов с запада на восток. Он решил построить в пределах этого участка дом размером a квадратов с севера на юг и b с запада на восток. Некоторые квадраты радиоактивны, и Петр не хочет на них строить дом. Кроме того, Петр хочет, чтобы расстояния от стен до границ участка выражалась целым числом квадратов. Долго выбирал он место для дома, но так и не выбрал – слишком много вариантов. А сколько? Начал наш герой считать, но не сумел – плохо математику учил. Помогите ему.

Вход. Сначала заданы числа m, n, a, b, k (1 ≤ a ≤ m ≤ 5000, 1 ≤ b ≤ n ≤ 5000, 0 ≤ k ≤ m * n), где m, n – размеры участка, a и b – размеры дома, k – количество радиоактивных квадратов. Далее следуют k неповторяющихся пар чисел i и j (1 ≤ i ≤ m, 1 ≤ j ≤ n), которые определяют координаты радиоактивных квадратов.

Выход. Выведите искомое количество способов расположения дома.

Пример входа 1	Пример выхода 1
5 7 2 4 3 2 5 3 3 3 6	5
Пример входа 2	Пример выхода 2
4 4 2 2 6 1 1 1 3 2 2 2 4 3 4 4 1	1

РЕШЕНИЕ

динамическое программирование

Анализ алгоритма

Заведем двумерный массив mas[5001][5001], в который внесем информацию о радиоактивном загрязнении участка. Положим mas[i][j] = 1, если ячейка (i, j) заражена и mas[i][j] = 0 иначе.

Далее пересчитаем ячейки массива mas так, чтобы mas[i][j] содержало количество радиоактивных ячеек в прямоугольнике (0, 0) – (i, j). Это можно сделать при помощи двойного цикла по i и j. Например, пусть значения mas[x][y] для всех 1 ≤ x ≤ i, 1 ≤ y ≤ j кроме mas[i][j] уже пересчитаны. Тогда mas[i][j] = mas[i][j] + mas[i – 1][j] + mas[i][j – 1] – mas[i – 1][j – 1].

Далее перебираем все возможные левые верхние углы дома (i, j), где 1 ≤ i ≤ m – a + 1, 1 ≤ j ≤ n – b + 1, и проверяем, содержится ли хоть одна радиоактивная клетка на месте дома. Дом можно построить (прямоугольник не содержит радиоактивных клеток), если значение выражения

mas[i + a – 1][j + b – 1] + mas[i – 1][j – 1] – mas[i – 1][j + b – 1] – mas[i + a – 1][j – 1]

равно нулю.

Пример

Рассмотрим второй тест. Слева представлено содержимое массива mas после чтения входных данных. Справа содержатся значения элементов массива mas после пересчета.

Дом 2 на 2 можно построить в единственном месте – в позиции (i, j) = (2, 1) (позиции нумеруются с 0). Действительно, имеем:

mas[3][2] + mas[1][0] – mas[3][0] – mas[1][2] = 4 + 1 – 2 – 3 = 0

Реализация алгоритма

Объявим двумерный массив mas. В переменной res будем подсчитывать количество способов расположения дома.

#define MAX 5001

int mas[MAX][MAX], res;

Читаем входные данные.

scanf("%d %d %d %d %d",&m,&n,&a,&b,&k);

memset(mas,0,sizeof(mas));

for(res = i = 0; i < k; i++)

{

scanf("%d %d",&x,&y);

mas[x][y] = 1;

}

Пересчитаем ячейки массива так, чтобы mas[i][j] содержало количество радиоактивных ячеек в прямоугольнике (0, 0) – (i, j).

for(i = 1; i <= m; i++)

for(j = 1; j <= n; j++)

mas[i][j] = mas[i][j] + mas[i-1][j] + mas[i][j-1] - mas[i-1][j-1];

Перебираем все возможные левые верхние углы дома (i, j), и проверяем, содержится ли хоть одна радиоактивная клетка на месте дома. Если ответ отрицательный, то на указанном месте можно построить дом. В этом случае увеличиваем значение переменной res на 1.

for(i = 1; i <= m - a + 1; i++)

for(j = 1; j <= n - b + 1; j++)

if (mas[i+a-1][j+b-1] + mas[i-1][j-1] –

mas[i-1][j+b-1] - mas[i+a-1][j-1] == 0) res++;

Выводим ответ.

printf("%d\n",res);

Java реализация

import java.util.*;

public class Main

{

static int mas[][];

public static void main(String[] args)

{

Scanner con = new Scanner(System.in);

int m = con.nextInt();

int n = con.nextInt();

int a = con.nextInt();

int b = con.nextInt();

int k = con.nextInt();

mas = new int[m+1][n+1];

int res = 0;

for(int i = 0; i < k; i++)

{

int x = con.nextInt();

int y = con.nextInt();

mas[x][y] = 1;

}

for(int i = 1; i <= m; i++)

for(int j = 1; j <= n; j++)

mas[i][j] = mas[i][j] + mas[i-1][j] + mas[i][j-1] - mas[i-1][j-1];

for(int i = 1; i <= m - a + 1; i++)

for(int j = 1; j <= n - b + 1; j++)

if (mas[i+a-1][j+b-1] + mas[i-1][j-1] - mas[i-1][j+b-1] - mas[i+a-1][j-1] == 0) res++;

System.out.println(res);

con.close();

}

}