Spreading
Lesson 31 of 32 in Coddy's Coding Problems course.
Challenge
HardIn one neighborhood every neighbor copies the color of the houses painted gray. So on the day that some houses are painted gray, every neighbor next to those houses horizontally and vertically decides to paint their house the same way. They need one month for that. After that the houses next to them horizontally and vertically decide to do the same thing, and they take one month as well, and so on.
####X ##XXX #XXXX XXXXX
##X## #XXXX XXXXX XXXXX
##### ##X## #XXXX XXXXX
Mo.1 Mo.2 Mo.3 Mo.4
As you can see, in the beginning only two houses are painted gray ([1,5] and [2,3]). After a month, 8 houses are painted gray, the ones above, below, on the right and on the left of the already painted houses. After two months 13 houses are painted gray and after 3 months every house in the neighborhood is painted gray.
You are given two natural number H and W from input, representing the height and width of the neighborhood. In the next line you are given a natural number N representing the number of houses that need to be painted gray. In the next line you are given a natural number M, in the next M lines you are given to natural numbers X and Y representing the positions of the houses that already painted gray.
Output how many months are need for a total of N houses to be painted gray (including the houses that are initially painted gray).
Input
3 5
7
2
1 5
2 3
Output
1
Explanation #1: We have the example from given in the text above. So, the neighborhood has a height 3 and width 5. We need to output how many months are needed for a total of 7 houses to be painted gray. There are 2 houses already painted gray they are on the positions [1, 5] and [2,3]. So, one month is needed for a total of 7 houses to be painted gray.
Try it yourself
#include <stdio.h>
int main() {
// Write code here
return 0;
}
All lessons in Coding Problems
1Course Introduction
Introduction