Ev (Həll təhlili)

İki ölçülü $mas[5001][5001]$ massivi elan edək, burada sahənin radioaktiv çirklənməsi haqqında məlumatı saxlayacağıq. Tutaq ki, mas[i][j] = 1, əgər $(i,j)$ xanası çirklənibsə, və mas[i][j] = 0 əks halda.

Sonra $mas$ massivini elə çevirək ki, mas[i][j] $(1,1)$ və $(i,j)$ künclü düzbucaqlıdakı radioaktiv xanaların sayını saxlasın. Bunu $i$ və $j$ üzrə ikiqat dövrə ilə etmək olar. Tutaq ki, mas[x][y] dəyərləri mas[i][j] istisna olmaqla bütün 1 \le x \le i, 1 \le y \le j üçün artıq yenidən hesablanıb. Onda aşağıdakı düstur doğrudur:

Bundan sonra evin sol yuxarı küncünün bütün mümkün mövqelərini $(i,j)$, burada 1 \le i \le m - a + 1, 1 \le j \le n - b + 1, sıralayacağıq və müvafiq düzbucaqlıda heç olmasa bir radioaktiv xananın olub-olmadığını yoxlayacağıq.

Ev tikmək olar (yəni seçilmiş düzbucaqlı radioaktiv xanalar ehtiva etmir), əgər

ifadəsinin dəyəri sıfıra bərabərdirsə.

Nümunə

İkinci testi nəzərdən keçirək. Solda giriş məlumatları oxunduqdan sonra $mas$ massivinin məzmunu, sağda isə yenidən hesablamadan sonra bu massivin elementlərinin dəyərləri göstərilmişdir.

$2$-yə $2$ ölçülü ev yalnız bir yerdə yerləşdirilə bilər – sol yuxarı künc (i, j) = (3, 2) mövqeyində (mövqelərin nömrələnməsi $1$-dən başlayır). Həqiqətən də:

Alqoritmin reallaşdırılması

İki ölçülü $mas$ massivi elan edək. $res$ dəyişənində evin yerləşdirilməsinin mümkün üsullarının sayını hesablayacağıq.

#define MAX 5001
int mas[MAX][MAX], res;

Giriş məlumatlarını oxuyuruq.

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

Massivin elementlərini elə yenidən hesablayaq ki, mas[i][j] $(1,1)$ və $(i,j)$ künclü düzbucaqlıdakı radioaktiv xanaların sayını saxlasın.

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];

Evin sol yuxarı küncünün bütün mümkün koordinatlarını $(i,j)$ sıralayırıq və evə uyğun sahədə heç olmasa bir radioaktiv xananın olub-olmadığını yoxlayırıq. Əgər belə xanalar yoxdursa, o zaman bu yerdə ev tikmək olar. Bu halda $res$ dəyişəninin dəyərini $1$ artırırıq.

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++;

Cavabı çıxarırıq.

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

Java reallaşdırması

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();
  }
}