Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

COLOR11 - Colorindo

 

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 ≤ iN e 1 ≤ jM. 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.

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. 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, 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.

Restrições

  • 1 ≤ N, M ≤ 200.
  • 1 ≤ K ≤ 10 000.
  • 1 ≤ X, AN.
  • 1 ≤ Y, BM.

Exemplos

Entrada
1 5 1 2 2
1 1
1 4

Saída
2

Entrada
5 5 3 3 7
2 2
2 3
2 4
3 2
3 4
4 2
4 3

Saída
18

Neste exemplo de caso de teste, 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).

Entrada
10 10 5 5 22
2 2
2 3
2 4
2 5
2 6
2 7
2 8
3 2
3 8
4 2
4 8
5 2
5 8
6 2
6 8
7 2
7 3
7 4
7 5
7 6
7 7
7 8

Saída
20

Neste exemplo de caso de teste, 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.


Adicionado por:Wanderley Guimarăes
Data:2012-03-10
Tempo limite:1s
Tamanho do fonte:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Linguagem permitida:Todas exceto: ASM64 CLOJURE ERL FSHARP PERL6 PY_NBC SCALA TCL
Origem:OBI 2011 - fase 2 nível 1

hide comments
2016-05-02 16:31:00 Elsio [UFABC]
Floodfill simples! (Com diagonal)
2012-05-01 01:50:19 William Lopes [UFV-CF]
Esse me deu uma dor de cabeça, mas valeu! =)
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.