Solucionando o problema \"Colorindo\"

Colorindo David D´eharbe 16 de Abril de 2015

1

Introdu¸ c˜ ao

Este documento apresenta uma solu¸c˜ao ao problema ’Colorindo’, proposto na segunda fase da edi¸c˜ ao 2011 da Olimp´ıada Brasileira de Inform´atica, no n´ıvel 1. O problema consiste em determinar quantas posi¸c˜oes de uma grade s˜ao coloridas por uma crian¸ca. A grade pode ter at´e 200 linhas e colunas, e algumas posi¸c˜ oes s˜ ao marcadas como cheias. A crian¸ca come¸ca a colorir a partir de uma posi¸c˜ ao inicial dada, e continua colorindo repetidamente as posi¸c˜oes vizinhas, desde que estas n˜ ao estejam cheias. As c´elulas nas diagonais s˜ao consideradas vizinhas, e uma posi¸c˜ ao tem at´e oito posi¸c˜oes vizinhas. O programa que soluciona este problema est´a estruturado da seguinte maneira: 1

h Arquivos cabe¸calhos a incluir 2 i h Constantes globais 4 i h Vari´ aveis globais 5 i h Sub-rotinas 8 i h Programa principal 10 i

1

2

Arquivos cabe¸calhos

Precisamos das sub-rotinas padr˜ao scanf e printf de leitura e escrita. Tamb´em usaremos a sub-rotina memset da biblioteca padr˜ao para inicializar o conte´ udo de um arranjo bi-dimensional em um comando s´o. 2

h Arquivos cabe¸calhos a incluir 2 i ≡ #include #include This code is used in chunk 1.

2

3

Constantes

Cada posi¸c˜ ao da grade pode estar em um de trˆes estados poss´ıveis: • CHEIO isso ´e definido na entrada • VAZIO ´e o estado por defaut • PINTADO ´e a posi¸c˜ ao onde a crian¸ca come¸ca a pintar, ou qualquer posi¸c˜ao alcan¸c´ avel a partir da posi¸c˜ao inicial segundo as regras do jogo. S˜ ao ent˜ ao apenas trˆes valores poss´ıveis, e lan¸caremos m˜ao do tipo char para representar eles, e dos valores 0, 1 e 2 para codificar cada um dos estados poss´ıveis. Definimos trˆes nomes para cada um desses n´ umeros, utilizando a diretiva define. 3

#define VAZIO 0 /∗ valor defaut: n˜ao pintada, nem cheia ∗/ #define CHEIO 1 /∗ posi¸c˜ao cheia: n˜ao pode ser pintada ∗/ #define PINTADO 2 /∗ posi¸c˜ao j´a pintada ∗/ ¶ A tabela D ser´ a utilizada para calcular as posi¸c˜oes vizinhas de uma dada posi¸c˜ ao. Como s˜ ao at´e oito posi¸c˜oes vizinhas, D tem oito entradas. Cada uma dessas entradas armazena a diferen¸ca entre cada coordenada da posi¸c˜ao inicial com uma das suas vizinhas:

4

h Constantes const int {−1, 0}, {−1, 1}, {0, 1}, {1, 1}, {1, 0}, {1, −1}, {0, −1} };

globais 4 i ≡ D[8][2] = {{−1, −1}, /∗ oeste ∗/ /∗ sudoeste ∗/ /∗ sul ∗/ /∗ suleste ∗/ /∗ leste ∗/ /∗ nordeste ∗/ /∗ norte ∗/

/∗ noroeste ∗/

This code is used in chunk 1.

3

4

Dados

A descri¸c˜ ao do problema informa explicitamente algumas quantidades que o programa vai representar atrav´es de vari´aveis globais homˆonimas: Os n´ umeros inteiros N e M s˜ao respectivamente o n´ umero de linhas e colunas da grade, enquanto que (X, Y ) ´e a coordenada onde a crianca vai comecar a pintar e K ´e o numero de quadrados cheios na figura. 5

h Vari´ aveis globais 5 i ≡ int N ; /∗ n´ umero de linhas ∗/ int M ; /∗ n´ umero de colunas ∗/ int K; /∗ n´ umero de posi¸c˜oes cheias ∗/ int X; /∗ linha da posi¸c˜ao inicial ∗/ int Y ; /∗ coluna da posi¸c˜ao inicial ∗/ See also chunk 6. This code is used in chunk 1.

¶ Adicionalmente, o programa representa o estado da grade sendo pintada atrav´es de um arranjo de arranjos. O m´aximo de linhas e de colunas, de acordo com a descri¸c˜ ao do problema, ´e 200. Ent˜ao ´e declarado um arranjo bi-dimensional, chamado grade , com as dimens˜oes m´aximas poss´ıveis. O valor de grade [x][y] ´e um entre CHEIO, VAZIO e PINTADO. Como s˜ao apenas trˆes valores poss´ıveis, utilizaremos o tipo inteiro char como o tipo dos elementos deste arranjo. 6

h Vari´ aveis globais 5 i +≡ char grade [200][200];

/∗ conte´ udo da grade a ser pintada ∗/

4

5

Sub-rotinas

¶ A sub-rotina pintar grade tem como papel pintar a grade a partir de uma posi¸c˜ ao dada, seguindo as regras enunciadas na descri¸c˜ao do problema. Tem como parˆ ametros as coordenadas, digamos X e Y , de uma posi¸c˜ao inicial a ser pintada. Assumimos que estas coordenadas s˜ao as de uma posi¸c˜ao legal da grade (n˜ ao negativas, e dentro dos limites), e que esta posi¸c˜ao ´e vazia. O resultado da chamada ser´ a de alterar todas as posi¸c˜oes alcan¸c´aveis a partir das coordenadas iniciais, desde que estejam “vazias”. A estrat´egia para alcan¸car todas as posi¸c˜oes poss´ıveis ´e de aplicar recursivamente o procedimento pintar grade a cada uma das posi¸c˜ oes vizinhas que seja legal e “vazia”. 8

h Sub-rotinas 8 i ≡ void pintar grade (const int X, const int Y ) { grade [X][Y ] = PINTADO; int i; for (i = 0; i < 8; ++ i) { int X2 = X + D[i][0]; int Y2 = Y + D[i][1]; if (1 ≤ X2 ∧ X2 ≤ N ∧ 1 ≤ Y2 ∧ Y2 ≤ M ∧ grade [X2][Y2] ≡ VAZIO) pintar grade (X2, Y2); } } See also chunk 9. This code is used in chunk 1.

¶ A sub-rotina contar pintados tem como papel contar quantas posi¸c˜oes na tabela est˜ ao pintadas. N˜ ao tem parˆametros e retorna a quantidade de posi¸c˜oes em grade cujo valor ´e igual a PINTADO: 9

h Sub-rotinas 8 i +≡ int contar pintados (void) { int soma ; int linha ; int coluna ; soma = 0; for (linha = 1; linha ≤ N ; ++ linha ) { for (coluna = 1; coluna ≤ M ; ++ coluna ) { if (grade [linha ][coluna ] ≡ PINTADO) soma += 1; } } return soma ; }

5

6

Programa principal

O programa principal est´ a contido na sub-rotina main e est´a dividido em cinco etapas: 10

h Programa principal 10 i ≡ main (void) { h Preenchimento do conte´ udo de grade 11 i; h Leitura da primeira linha da entrada 12 i; h Leitura das K linhas seguintes 13 i; h Colorir a grade a partir das coordenadas X, Y 14 i; h Calcula quantas posi¸co˜es foram pintadas e imprime o resultado 15 i; return 0; } This code is used in chunk 1.

¶ O programa principal primeiramente lˆe uma instˆancia do problema. A entrada apenas informa as posi¸c˜oes cheias, todas as demais est˜ao inicialmente vazias. Logo, o conte´ udo de grade ´e inicialmente preenchido com o valor VAZIO. Isso poderia ser feito com dois la¸cos aninhados que percorrem todas as posi¸c˜oes poss´ıveis. Uma chamada ` a sub-rotina padr˜ao memset realiza esta inicializa¸c˜ao, assumindo que a grade tem as dimens˜oes m´aximas poss´ıveis. 11

h Preenchimento do conte´ udo de grade 11 i ≡ memset (grade , VAZIO, sizeof (char) ∗ 200 ∗ 200); This code is used in chunk 10.

¶ A primeira linha da entrada fornece as dimens˜oes N e M da grade, a posi¸c˜ao X, Y onde come¸car a colorir, e o n´ umero K de c´elulas cheias. 12

h Leitura da primeira linha da entrada 12 i ≡ scanf ("%i %i %i %i %i", &N , &M , &X, &Y , &K); This code is used in chunk 10.

¶ As K linhas seguintes contem as coordenadas das c´elulas cheias. Essas s˜ ao lidas, e a posi¸c˜ ao correspondente em grade ´e alterada para CHEIO. As coordenadas s˜ ao ajustadas para levar em conta o fato que os ´ındices do arranjo inicializam com zero, enquanto que as coordenadas come¸cam a contar a partir de um. 13

h Leitura das K linhas seguintes 13 i ≡ int i; for (i = 0; i < K; int A, B;

++ i)

{

6

scanf ("%i %i", &A, &B); grade [A − 1][B − 1] = CHEIO; } This code is used in chunk 10.

¶ Uma vez que a instˆ ancia do problema foi lida e representada em mem´oria, prossegue-se pintando a grade, utilizando a sub-rotina pintar grade . 14

h Colorir a grade a partir das coordenadas X, Y 14 i ≡ pintar grade (X, Y ); This code is used in chunk 10.

¶ Em seguida, ´e calculado o n´ umero de posi¸c˜oes pintadas, com a sub-rotina ao impresso. contar pintados , que ´e ent˜ 15

h Calcula quantas posi¸c˜ oes foram pintadas e imprime o resultado 15 i ≡ printf ("%i\n", contar pintados ( )); This code is used in chunk 10.

7

´Indice Eis uma rela¸c˜ ao dos identificadores utilizados, e os locais onde aparecem. Entradas sub-linhadas indicam o local de defini¸c˜ao. A: 13. B: 13. CHEIO: 3, 6, 13. coluna : 9. contar pintados : 9, 15. D: 4. grade : 6, 8, 9, 11, 13. i: 8, 13. K: 5. linha : 9. M : 5. main : 10. memset : 2, 11. N : 5. PINTADO: 3, 6, 8, 9. pintar grade : 8, 14. printf : 2, 15. scanf : 2, 12, 13. soma : 9. VAZIO: 3, 6, 8, 11. X: 5, 8. X2: 8. Y : 5, 8. Y2: 8.

8

List of Refinements h Arquivos cabe¸calhos a incluir 2 i Used in chunk 1. h Calcula quantas posi¸c˜ oes foram pintadas e imprime o resultado 15 i Used in chunk 10.

h Colorir a grade a partir das coordenadas X, Y 14 i Used in chunk 10. h Constantes globais 4 i Used in chunk 1. h Leitura da primeira linha da entrada 12 i Used in chunk 10. h Leitura das K linhas seguintes 13 i Used in chunk 10. h Preenchimento do conte´ udo de grade 11 i Used in chunk 10. h Programa principal 10 i Used in chunk 1. h Sub-rotinas 8, 9 i Used in chunk 1. h Vari´ aveis globais 5, 6 i Used in chunk 1.

9