Spreading
Урок 31 из 32 курса Задачи по программированию на Coddy.
Задание
СложноВ одном районе каждый сосед копирует цвет домов, выкрашенных в серый цвет. Таким образом, в тот день, когда некоторые дома красят в серый цвет, каждый сосед, живущий рядом с этими домами по горизонтали и вертикали, решает покрасить свой дом так же. На это им требуется один месяц. После этого дома, расположенные рядом с ними по горизонтали и вертикали, решают сделать то же самое, и это тоже занимает один месяц, и так далее.
####X ##XXX #XXXX XXXXX
##X## #XXXX XXXXX XXXXX
##### ##X## #XXXX XXXXX
Mo.1 Mo.2 Mo.3 Mo.4
Как видите, в начале только два дома покрашены в серый цвет ([1,5] и [2,3]). Через месяц в серый цвет покрашены 8 домов — те, что находятся сверху, снизу, справа и слева от уже покрашенных домов. Через два месяца в серый цвет покрашено 13 домов, а через 3 месяца каждый дом в районе покрашен в серый цвет.
Вам даны два натуральных числа H и W на входе, представляющие высоту и ширину района. В следующей строке дано натуральное число N, представляющее количество домов, которые должны быть покрашены в серый цвет. В следующей строке дано натуральное число M, в следующих M строках даны два натуральных числа X и Y, представляющие координаты домов, которые уже покрашены в серый цвет.
Выведите, сколько месяцев потребуется, чтобы в общей сложности N домов были покрашены в серый цвет (включая дома, которые были покрашены изначально).
Ввод
3 5
7
2
1 5
2 3
Вывод
1
Пояснение №1: У нас есть пример, приведенный в тексте выше. Итак, район имеет высоту 3 и ширину 5. Нам нужно вывести, сколько месяцев потребуется, чтобы в общей сложности 7 домов были покрашены в серый цвет. Уже покрашены 2 дома, они находятся в позициях [1, 5] и [2,3]. Таким образом, требуется один месяц, чтобы в общей сложности 7 домов были покрашены в серый цвет.
Попробуйте сами
#include <stdio.h>
int main() {
// Напишите код здесь
return 0;
}
Все уроки раздела Задачи по программированию
1Course Introduction
Introduction