uCoder | 1006 | Nível: 3 | Tempo Limite: 10
Paint não, filho!
Adaptado por erich.rodriguesf
Competição: Interfatecs 2014 1ª fase
Kaio Damásio Ernane, o famoso KDE, recebeu seu nome numa homenagem prestada pelo seu pai, um professor de Computação fanático por Linux, ao ambiente desktop deste sistema operacional que leva o mesmo nome. Para o pai de Kaio, o Windows e tudo feito para ele não presta.
Em toda oportunidade que tem, o pai de Kaio procura desmerecer o Windows. É piada para cá e para lá: “Windows é igual rodízio de carros. Quando você começa a entender, vem alguém e muda tudo de novo...”, “O assistente do Windows é como irmão mais novo, tá sempre enchendo o saco...”, “O Windows é tão lento, tão lento, que não tem tempo de resposta, tem prazo de entrega...”, e por aí vai.
Ironicamente, o KDE tem uma certa queda pelo Windows e, quando seu pai não está por perto, abre o sistema numa máquina virtual escondida no seu Ubuntu, e passa horas se divertindo. Quando era pequeno, o pai de KDE o encontrou escrevendo um documento no WordPad em pleno dia de Natal. Foi a maior tristeza! Durante a ceia, ficou comentando com os amigos “Poxa... você não sabe o que me aconteceu hoje...” e contava o ocorrido com o filho.
Quando KDE cresceu e entrou no curso de ADS da Fatec Mogi, para dar uma lição no filho, seu pai passou a lhe dar castigos quando o encontrava mexendo no Windows: “Lembra quando você mexeu com Wordpad? Então... vai ter que implementar um editor de textos melhor que ele para o Linux”. E assim foi para toda vez que ele pegou KDE mexendo no Windows.
Na última semana, após chegar do trabalho, o pai de KDE o pegou fazendo um desenho no Paint. Foi um grito que o bairro inteiro escutou: “Paint não! Filho. Paint não!” e logo veio o castigo: implementar uma versão melhor que o Paint para o Linux.
Apesar de ter resolvido com facilidade os últimas castigos, desta vez, KDE está com uma dúvida. Ele está implementando um algoritmo similar ao da lata de tinta do Paint. Em resumo, quando um usuário clica com o mouse sobre um pixel de uma imagem, a lata de tinta preenche todos os pixels que possuem exatamente a mesma cor e que estão na 4-vizinhaça do pixel em questão e faz isso em seguida com os pixels pintados e assim por diante. A 4-vizinhança é o conjunto de pixels que se encontram acima, abaixo, à esquerda ou à direita do atual.
Na figura seguinte (à esquerda), por exemplo, assumindo que o primeiro pixel (canto superior esquerdo) está na linha 1, coluna 1, caso o usuário clique com a lata de tinta sobre o pixel (4,5) – linha 4, coluna 5 -, 10 pixels serão pintados – eles estão destacados na figura da direita.
|
|
KDE pediu sua ajuda para escrever um algoritmo que, dada uma matriz que representa uma imagem, com L linhas e C colunas, os valores das células desta matriz, que representam cores e um pixel onde será aplicada a lata de tinta, retorna o número de pixels que serão preenchidos por meio da lata de tinta.
Entrada
A entrada é composta por vários casos de teste. A primeira linha de cada caso de teste contém dois números inteiros L (1 ≤ L ≤ 1000) e C (1 ≤ C ≤ 1000), representando o número de linhas e colunas da imagem, respectivamente. As próximas L linhas da entrada contêm C números inteiros cada, com valores maiores ou iguais a 0 e menores ou iguais a 255, representando os valores dos pixels da imagem. A próxima linha da entrada contém dois números inteiros X (1 ≤ X ≤ L) e Y (1 ≤ Y ≤ C), representando a linha e coluna do pixel onde será aplicada lata de tinta, respectivamente. O pixel do canto superior esquerdo da imagem é considerado como estando na posição (1,1). A entrada termina quando forem informados valores L e C iguais a 0.
Saída
Para cada caso de teste, imprima um número inteiro Q (1 ≤ Q ≤ 1000000) representando o número de pixels que serão pintados pela lata de tinta.
| Exemplo de Entrada | Exemplo de Saída |
|---|---|
|
7 6 |
10 |