10703. Свободные места

Задана доска и множество прямоугольников на ней. Найти количество клеток на доске, которые не содержатся ни в одном прямоугольнике.

Вход. Содержит несколько тестов, разделенных друг от друга пустой строкой. Первая строка теста содержит ширину w и высоту h доски, а также количество прямоугольников n на доске (1 £ w, h £ 500, 0 £ n £ 99). Далее следуют n строк с числами x1, y1, x2, y2, описывающих прямоугольники координатами их противоположных углов (x1, y1) – (x2, y2). Известно, что 1 £ x1, x2 £ w, 1 £ y1, y2 £ h. Обработка входных данных завершается, когда w = h = n = 0.

Выход. Для каждого теста вывести количество клеток на доске, не ограниченных ни одним прямоугольником в соответствии с форматом, показанном в примере.

Пример входа

1 1 1
1 1 1 1
 
2 2 2
1 1 1 2
1 1 2 1
 
493 182 3
349 148 363 146
241 123 443 147
303 124 293 17
 
0 0 0

Пример выхода

There is no empty spots.
There is one empty spot.
There are 83470 empty spots.

РЕШЕНИЕ

заполнение

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

Объявим двумерный массив rect, заполним его нулями. Для каждого прямоугольника будем отмечать в этом массиве точки, покрытые им. Клетка (i, j) считается покрытой каким – нибудь прямоугольником, если rect[i][j] = 1 и непокрытой, если rect[i][j] = 0. Для нахождения ответа достаточно подсчитать количество непокрытых клеток после обработки всех прямоугольников.

Пример

Во втором тесте имеется доска размером 2 ´ 2 и два прямоугольника. Клетки, которые покрывают прямоугольники, закрашены черным цветом. Незакрашенным остается один квадрат.

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

Доску будем сохранять в массиве int rect[501][501]. Поскольку 1 £ w, h £ 500, то для хранения поля следует объявить массив размера 501 (от 0 до 500).

Функция swap меняет элементы x и y местами.

void swap(int *x, int *y)

{

int i = *x; *x = *y; *y = i;

}

Читаем размеры доски w, h и количество заданных на ней прямоугольников n.

while (scanf("%d %d %d",&w,&h,&n),w + h + n != 0)

{

Обнулим массив rect, который сохраняет состояние клеток доски. Для каждого прямоугольника (x1, y1) – (x2, y2) упорядочим координаты его концов так, чтобы (x1, y1) был левым нижним углом, а (x2, y2) – верхним правым. Для этого необходимо чтобы выполнялись неравенства x1 £ x2, y1 £ y2. Далее положим rect[i][j] = 1 для всех x1 £ i £ x2, y1 £ j £ y2.

memset(rect,0,sizeof(rect));

for(k = 0; k < n; k++)

{

scanf("%d %d %d %d",&x1,&y1,&x2, &y2);

if (x1 > x2) swap(&x1,&x2);

if (y1 > y2) swap(&y1,&y2);

for(i = x1; i <= x2; i++)

for(j = y1; j <= y2; j++) rect[i][j] = 1;

}

Подсчитываем количество непокрытых квадратов в переменной k и печатаем ответ в соответствии с требуемым форматом.

k = 0;

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

for(j = 1; j <= h; j++) if (!rect[i][j]) k++;

switch(k){

case 0:printf("There is no empty spots.\n");break;

case 1:printf("There is one empty spot.\n");break;

default:printf("There are %d empty spots.\n",k);

}

}