Будинок#764

Будинок (Розбір)

Оголосимо двовимірний масив $ma s [5001] [5001]$ , в якому зберігатимемо інформацію про радіоактивне забруднення ділянки. Нехай $ma s [i] [j] = 1$ mas[i][j] = 1, якщо клітинка $(i, j)$ заражена, і $ma s [i] [j] = 0$ mas[i][j] = 0 в іншому випадку.

Далі перетворимо масив $ma s$ так, щоб $ma s [i] [j]$ mas[i][j] містило кількість радіоактивних клітинок у прямокутнику з кутами $(1, 1)$ та $(i, j)$ . Це можна зробити за допомогою подвійного циклу по $i$ та $j$ . Припустимо, що значення $ma s [x] [y]$ mas[x][y] вже перераховані для всіх $1 \leq x \leq i, 1 \leq y \leq j$ 1 \le x \le i, 1 \le y \le j, крім $ma s [i] [j]$ mas[i][j]. Тоді виконується наступна формула:

ma s [i] [j] = ma s [i] [j] + ma s [i -1] [j] + ma s [i] [j - 1] - ma s [i - 1] [j - 1]

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

Після цього переберемо всі можливі позиції лівого верхнього кута будинку $(i, j)$ , де $1 \leq i \leq m - a + 1, 1 \leq j \leq n - b + 1$ 1 \le i \le m - a + 1, 1 \le j \le n - b + 1, і перевіримо, чи є у відповідному прямокутнику хоча б одна радіоактивна клітинка.

Будинок можна побудувати (тобто вибраний прямокутник не містить радіоактивних клітинок), якщо значення виразу

ma s [i + a - 1] [j + b - 1] + ma s [i - 1] [j - 1] - ma s [i - 1] [j + b - 1] - ma s [i + a - 1] [j - 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]

дорівнює нулю.

Приклад

Розглянемо другий тест. Ліворуч показано вміст масиву $ma s$ після читання вхідних даних, а праворуч – значення елементів цього масиву після перерахунку.

Будинок розміром $2$ на $2$ можна розмістити лише в одному місці – з лівим верхнім кутом у позиції $(i, j) = (3, 2)$ (i, j) = (3, 2) (нумерація позицій починається з $1$ ). Справді, маємо:

ma s [4] [3] + ma s [2] [1] - ma s [4] [1] - ma s [2] [3] = 4 + 1 - 2 - 3 = 0

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

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

Оголосимо двовимірний масив $ma s$ . У змінній $r es$ підраховуватимемо кількість способів розташування будинку.

#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;
}

C++

Перерахуємо елементи масиву так, щоб $ma s [i] [j]$ mas[i][j] містило кількість радіоактивних клітинок у прямокутнику з кутами $(1, 1)$ та $(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)$ і перевіряємо, чи є хоча б одна радіоактивна клітинка на ділянці, що відповідає будинку. Якщо таких клітинок немає, то в цьому місці можна побудувати будинок. У цьому випадку збільшуємо значення змінної $r es$ на $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();
  }
}

Java