Algorithm
Problem Name: 2 AD-HOC - beecrowd | 2405
Problem Link: https://www.beecrowd.com.br/judge/en/problems/view/2405
Colorindo
Por OBI - Olimpíada Brasileira de Informática 2011 
Brazil
Timelimit: 1
A Sociedade Brasileira das Cores (SBC) é uma editora de livros de colorir. As crianças adoram os livros da SBC porque suas figuras, depois de pintadas, ficam muito coloridas e bonitas. Isso acontece porque a SBC se preocupa em não deixar grandes regiões contínuas em suas figuras, que devem ser pintadas com uma cor só.
Até agora, o processo de verificar se uma figura tinha uma região contínua grande era completamente visual, mas a SBC resolveu automatizar esse processo e você foi contratado para programar uma parte desse sistema.
Uma figura é representada por uma grade, de dimensão N por M. Cada quadrado dessa grade é representado por uma coordenada (i, j), com 1 ≤ i ≤ N e 1 ≤ j ≤ M. Por exemplo, a coordenada (1, 5) representa o quadrado na primeira linha e quinta coluna, enquanto que a coordenada (3, 7) representa o quadrado na terceira linha e sétima coluna. As linhas são contadas de baixo para cima e as colunas da esquerda para a direita.
Cada quadrado pode estar vazio ou cheio. Assumimos que uma criança só vai pintar sobre quadrados vazios e se ela pintar um quadrado de uma cor, ela irá pintar os oito vizinhos da mesma cor, desde que eles estejam vazios e que ela não saia da área da figura.
No segundo exemplo de caso de teste abaixo, temos uma figura de dimensões 5 × 5. A criança começa a pintar na posição (3, 3). Na figura abaixo ilustramos este caso. A posição que a criança inicia está marcada com a letra "X", e os quadrados que a criança consegue pintar estão destacandos em cinza claro. Note que ela consegue pintar o quadrado (4, 4), pois este quadrado é um dos quadrados que ela consegue pintar após ter pintado o quadrado (3, 3).
No terceiro exemplo de caso de teste abaixo, temos uma figura de dimensões 10 × 10. A criança começa a pintar na posição (5, 5). Na figura abaixo ilustramos este caso. A posição que a criança inicia está marcada com a letra "X", e os quadrados que a criança consegue pintar estão destacandos em cinza claro.
Dada a figura e a coordenada onde uma criança vai começar a pintar, sua tarefa é descobrir quantos quadrados ela irá pintar.
Entrada
A primeira linha da entrada contém 5 números inteiros, N, M, X, Y e K (1 ≤ N, M ≤ 200), (1 ≤ K ≤ 10 000). Os números inteiros N e M são respectivamente o número de linhas e colunas da grade, enquanto que (X, Y) é a coordenada onde a criança vai começar a pintar e K é o número de quadrados cheios na figura.
Seguem-se K linhas, cada uma com dois inteiros A e B (1 ≤ X, A ≤ N), (1 ≤ Y, B ≤ M) que são as coordenadas de um quadrado cheio.
Garantimos que o quadrado na posição (X, Y) está sempre vazio.
Saída
Seu programa deve imprimir uma linha contendo o número de quadrados pintados pela criança.
| Exemplos de Entrada | Exemplos de Saída |
|
1 5 1 2 2 1 1 1 4 |
2 |
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
#include <cstdio>
#include <vector>
#define MAXN 210
using namespace std;
int matriz[MAXN][MAXN], n, m, x, y, k, resposta;
void dfs(int a, int b) {
if (a < = 0 || b <= 0 || a > n || b > m) return;
if (matriz[a][b] == 0) {
matriz[a][b] = 1;
dfs(a + 1, b);
dfs(a - 1, b);
dfs(a, b + 1);
dfs(a, b - 1);
dfs(a + 1, b + 1);
dfs(a + 1, b - 1);
dfs(a - 1, b + 1);
dfs(a - 1, b - 1);
}
}
int main() {
scanf("%d %d %d %d %d", &n, &m, &x, &y, &k);
for (int i = 0; i < k; i++) {
int w, z;
scanf("%d %d", &w, &z);
matriz[w][z] = -1;
}
dfs(x, y);
for (int i = 1; i < = n; i++) {
for (int j = 1; j < = m; j++) {
if (matriz[i][j] == 1) resposta++;
}
}
printf("%d\n", resposta);
return 0;
}
Input
1 1
1 4