Spreading
Lição 31 de 32 do curso Problemas de Programação da Coddy.
Desafio
DifícilEm um bairro, cada vizinho copia a cor das casas pintadas de cinza. Assim, no dia em que algumas casas são pintadas de cinza, cada vizinho ao lado dessas casas, horizontal e verticalmente, decide pintar sua casa da mesma forma. Eles precisam de um mês para isso. Depois disso, as casas ao lado delas, horizontal e verticalmente, decidem fazer a mesma coisa, e levam um mês também, e assim por diante.
####X ##XXX #XXXX XXXXX
##X## #XXXX XXXXX XXXXX
##### ##X## #XXXX XXXXX
Mo.1 Mo.2 Mo.3 Mo.4
Como você pode ver, no início apenas duas casas estão pintadas de cinza ([1,5] e [2,3]). Após um mês, 8 casas estão pintadas de cinza, as que estão acima, abaixo, à direita e à esquerda das casas já pintadas. Após dois meses, 13 casas estão pintadas de cinza e após 3 meses todas as casas do bairro estão pintadas de cinza.
São fornecidos dois números naturais H e W da entrada, representando a altura e a largura do bairro. Na próxima linha, é fornecido um número natural N representando o número de casas que precisam ser pintadas de cinza. Na próxima linha, é fornecido um número natural M, e nas próximas M linhas são fornecidos dois números naturais X e Y representando as posições das casas que já estão pintadas de cinza.
Imprima quantos meses são necessários para que um total de N casas sejam pintadas de cinza (incluindo as casas que foram inicialmente pintadas de cinza).
Entrada
3 5
7
2
1 5
2 3
Saída
1
Explicação #1: Temos o exemplo fornecido no texto acima. Portanto, o bairro tem altura 3 e largura 5. Precisamos informar quantos meses são necessários para que um total de 7 casas sejam pintadas de cinza. Existem 2 casas já pintadas de cinza nas posições [1, 5] e [2,3]. Portanto, um mês é necessário para que um total de 7 casas sejam pintadas de cinza.
Experimente você mesmo
#include <stdio.h>
int main() {
// Escreva o código aqui
return 0;
}
Todas as lições de Problemas de Programação
1Course Introduction
Introduction