Task 90. Грядки
UniLecsЗадача: есть дачный участок размером M квадратов с севера на юг и N квадратов с запада на восток. Вам необходимо сделать новую грядку для свеклы размером А квадратов с севера на юг и B квадратов с запада на восток. Но некоторые квадраты уже заняты под грядки другими растениями. Расстояние от грядки до границ участка должно выражаться в целых квадратах (от нуля и более). Сколько возможных вариантов для расположения новой грядки под свеклу ?
Входные данные:
M, N - размер участка;
A, B - размер требуемой грядки под свеклу;
X, Y - массивы координат (x,y) квадратов, ктр уже заняты под другие грядки;
1 <= A <= M <= 5000, 1 <= B <= N <= 5000;
1 <= xi <= M, 1 <= yi <= N, (xi, yi) - координаты квадратов, ктр уже заняты под грядки.
Вывод: кол-во способов расположения новой грядки под свеклу
Пример:
M = N = 4;
A = B = 2;
[(1, 1), (1, 3), (2, 2), (2, 4), (3, 4), (4, 1)]
Answer: 1
Идея: заведем двумерный массив, в ктр будем хранить информацию о занятых квадратах. Arr[i, j] == 1, если ячейка (i,j) занята и Arr[i,j] == 0, если свободна.
Дальше пересчитаем ячейки массива таким образом, чтобы Arr[i,j] хранило информацию о кол-ве занятых ячеек в прямоугольнике (0,0) - (i,j).
И последний шаг: перебираем все возможные левые верхние углы грядки (i,j), где 1 <= i <= M - A + 1, 1 <= j <= N - B + 1, и проверяем, содержится ли хоть один занятый квадрат на месте новой грядки. Новую грядку можно расположить, если:
Arr[i + A - 1, j + B - 1] + Arr[i - 1, j - 1] - Arr[i - 1, j + B - 1] - Arr[i + A - 1, j - 1] = 0
Разберем пример, смотри рис.:
Здесь представлен массив после заполнения исходными данными (занятые квадраты помечены красным, зеленым - свободные).
На след.рисунке содержатся значения элементов массива после пересчета:
Новую грядку 2х2 можно расположить в единственном месте, начиная с позиции (3, 2), т.к. имеем по формуле:
Arr[4,3] + Arr[2,1] - Arr[4,1] - Arr[2,3] = 4 + 1 - 2 - 3 = 0
Реализация:
https://gist.github.com/unilecs/57334ba6eb5d3f1fe6d1baf15a5f3e9c
Test: