Google Code Jam 3009 - Watersheds

Vamos examinar agora o segundo problema da rodada de qualificação. Tive bastante dificuldade em enxergar uma forma de resolvê-lo, mas quando a achei a solução foi (na minha opinião) bastante eficiente.

O Problema

Resumindo o enunciado oficial:

• Devem ser resolvidos até 100 casos de testes (T).
• Em cada caso de teste é fornecido um mapa de elevação, que consiste em uma matriz de H linhas por W colunas de células. No small input o tamanho do mapa pode ser até 10x10 e no large input até 100x100.
  
• Para cada célula é fornecida a sua altitude, que é um número inteiro (0 a 9 no small input e 0 a 9999 no large input).
• Considera-se que a chuva que cai em cada célula irá ficar na célula ou fluir para uma das quatro células vizinhas (ao Norte, Sul, Leste e Oeste), conforme as altitudes delas. Se todas as células vizinhas tiverem altitude igual ou maior, a água ficará na célula que é considerada um dreno (sink). Caso contrário, a água irá pra a célula vizinha com altitude mais baixa. No caso de empate, escolhe-se a altitude mais baixa na ordem Norte, Oeste, Leste e Sul.
• Formam-se assim bacias, que são conjuntos de células cuja água flui, direta ou indiretamente para o mesmo dreno. No small input garante-se que existirão no máximo 2 bacias, no large input podem ser até 16.
  
• As bacias são identificadas por letras minúsculas de cima para baixo da direita para a esquerda.
• O resultado solicitado é uma tabela com as identificações das bacias de cada célula.

A melhor forma de entender o problema é examinando um exemplo, no caso com um mapa 3 x 3.
No primeiro desenho temos o mapa com as altitudes. As setas no segundo indicam a direção da água. As cores no terceiro mostram as bacias, que são identificadas com as letras no último desenho.

Minha Solução

Percorrer as células determinando a direção da água é bastante simples, a questão é como determinar as bacias.

Minha primeira ideia era ir agrupando as células em conjuntos à medida em que determinava o fluxo. O que atrapalhava esta ideia era a possibilidade de ter uma bacia em formato de U, onde eu estaria determinando dois conjuntos separados que mais adiante eu teria que agrupar.

A coisa simplificou bastante quando me veio a ideia de olhar o resultado do final para o começo, seguindo a água no sentido contrário ao fluxo. Partindo de cada dreno temos uma árvore onde cada pai tem no máximo quatro filhos. Aproveitando o exemplo anterior:

Meu algoritmo ficou o seguinte:

• Percorrer o mapa, determinando que são os drenos e marcando de onde vem a água para cada célula (o que cria as árvores).
• Numerar as bacias, partindo de cada dreno e percorrendo cada célula da árvore correspondente.
• Percorrer o mapa de cima para baixo, da esquerda para direita, para associar as letras corretas à numeração criada no item anterior.

Cada célula é armazenada em uma estrutura com os seguintes campos:

• altitude
• de onde vem a água (usei um bit para indicar cada uma das quatro direções possíveis)
• um flag que indica se é um dreno
• a bácia à qual a célula pertence
  

O código abaixo possui uma pequena alteração em relação ao que usei no Code Jam. Aqui map é uma matriz de duas dimensões, no meu código original era um vetor (matriz de uma dimensão) acessado através de lin*100+col (que no fundo é o código que o compilador vai gerar).

view plaincopy to clipboardprint?

1. //  
2. // Google CodeJam 2009 - Qualification Round, Problem B  
3. // DQuadros  
4. //  
5. #include <stdio.h>  
6. #include <stdlib.h>  
7. #include <string.h>  
8.   
9. typedef struct  
10. {  
11.    int     alt;  
12.    char    flows;  
13.    char    sink;  
14.    char    basin;  
15. } Cell;  
16.   
17. Cell map [100][100];  
18. char letter [26];  
19.   
20. #define FLOW_NORTH  1  
21. #define FLOW_WEST   2  
22. #define FLOW_EAST   4  
23. #define FLOW_SOUTH  8  
24.   
25. // recursive tree travel  
26. void mark (int l, int c, char b)  
27. {  
28.    map[l][c].basin = b;  
29.    if (map[l][c].flows & FLOW_NORTH)  
30.        mark (l-1, c, b);  
31.    if (map[l][c].flows & FLOW_SOUTH)  
32.        mark (l+1, c, b);  
33.    if (map[l][c].flows & FLOW_WEST)  
34.        mark (l, c-1, b);  
35.    if (map[l][c].flows & FLOW_EAST)  
36.        mark (l, c+1, b);  
37. }  
38.   
39. void main (void)  
40. {  
41.    int iCase, nCases;  
42.    int H, W;  
43.    int lin, col, i;  
44.    char b;  
45.    int neighb [4]; // North, West, East, South.  
46.    int min;  
47.   
48.    scanf ("%d\n", &nCases);  
49.    for (iCase = 1; iCase <= nCases; iCase++)  
50.    {  
51.        // read dimensions  
52.     scanf ("%d %d\n", &H, &W);  
53.   
54.        // init map  
55.        for (lin = 0; lin < H; lin++)  
56.        {  
57.            for (col = 0; col < W; col++)  
58.            {  
59.                scanf ("%d ", &map[lin][col].alt);  
60.                map[lin][col].sink = 0;  
61.                map[lin][col].flows = 0;  
62.            }  
63.        }  
64.   
65.        // determine flow  
66.        for (lin = 0; lin < H; lin++)  
67.        {  
68.            for (col = 0; col < W; col++)  
69.            {  
70.                // find to where it will flow  
71.                if (lin == 0)  
72.                    neighb [0] = 99999;  
73.                else  
74.                    neighb [0] = map[lin-1][col].alt;  
75.                if (col == 0)  
76.                    neighb [1] = 99999;  
77.                else  
78.                    neighb [1] = map[lin][col-1].alt;  
79.                if (col == (W-1))  
80.                    neighb [2] = 99999;  
81.                else  
82.                    neighb [2] = map[lin][col+1].alt;  
83.                if (lin == (H-1))  
84.                    neighb [3] = 99999;  
85.                else  
86.                    neighb [3] = map[lin+1][col].alt;  
87.                min = 0;  
88.                if (neighb [1] < neighb[min])  
89.                    min = 1;  
90.                if (neighb [2] < neighb[min])  
91.                    min = 2;  
92.                if (neighb [3] < neighb[min])  
93.                    min = 3;  
94.                if (map[lin][col].alt <= neighb[min])  
95.                {  
96.                    // it's a sink  
97.                    map[lin][col].sink = 1;  
98.                }  
99.                else  
100.                {  
101.                    // mark where it comes from  
102.                    switch (min)  
103.                    {  
104.                        case 0: // to North, from South  
105.                            map[lin-1][col].flows |= FLOW_SOUTH;  
106.                            break;  
107.                        case 1: // to West, from East  
108.                            map[lin][col-1].flows |= FLOW_EAST;  
109.                            break;  
110.                        case 2: // to East, from West  
111.                            map[lin][col+1].flows |= FLOW_WEST;  
112.                            break;  
113.                        case 3: // to South, from North  
114.                            map[lin+1][col].flows |= FLOW_NORTH;  
115.                            break;  
116.                    }  
117.                }  
118.   
119.            }  
120.        }  
121.   
122.        // follow trees from sink to upper lands  
123.        b = 0;  
124.        for (lin = 0; lin < H; lin++)  
125.        {  
126.            for (col = 0; col < W; col++)  
127.            {  
128.                if (map[lin][col].sink)  
129.                {  
130.                    mark (lin, col, b);  
131.                    b++;  
132.                }  
133.            }  
134.        }  
135.   
136.        // assign letters  
137.        for (i = 0; i < 26; i++)  
138.            letter[i] = 0;  
139.        b = 'a';  
140.        for (lin = 0; lin < H; lin++)  
141.        {  
142.            for (col = 0; col < W; col++)  
143.            {  
144.                if (letter [map[lin][col].basin] == 0)  
145.                    letter [map[lin][col].basin] = b++;  
146.            }  
147.        }  
148.   
149.        // print result  
150.  printf ("Case #%d:\n", iCase);  
151.        for (lin = 0; lin < H; lin++)  
152.        {  
153.            for (col = 0; col < W; col++)  
154.            {  
155.                i = lin*100+col;  
156.                if (col > 0)  
157.                    printf (" %c", letter [map[lin][col].basin]);  
158.                else  
159.                    printf ("%c", letter [map[lin][col].basin]);  
160.            }  
161.            printf ("\n");  
162.        }  
163.    }  
164. }  

//
// Google CodeJam 2009 - Qualification Round, Problem B
// DQuadros
//
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct
{
   int     alt;
   char    flows;
   char    sink;
   char    basin;
} Cell;

Cell map [100][100];
char letter [26];

#define FLOW_NORTH  1
#define FLOW_WEST   2
#define FLOW_EAST   4
#define FLOW_SOUTH  8

// recursive tree travel
void mark (int l, int c, char b)
{
   map[l][c].basin = b;
   if (map[l][c].flows & FLOW_NORTH)
       mark (l-1, c, b);
   if (map[l][c].flows & FLOW_SOUTH)
       mark (l+1, c, b);
   if (map[l][c].flows & FLOW_WEST)
       mark (l, c-1, b);
   if (map[l][c].flows & FLOW_EAST)
       mark (l, c+1, b);
}

void main (void)
{
   int iCase, nCases;
   int H, W;
   int lin, col, i;
   char b;
   int neighb [4]; // North, West, East, South.
   int min;

   scanf ("%d\n", &nCases);
   for (iCase = 1; iCase <= nCases; iCase++)
   {
       // read dimensions
    scanf ("%d %d\n", &H, &W);

       // init map
       for (lin = 0; lin < H; lin++)
       {
           for (col = 0; col < W; col++)
           {
               scanf ("%d ", &map[lin][col].alt);
               map[lin][col].sink = 0;
               map[lin][col].flows = 0;
           }
       }

       // determine flow
       for (lin = 0; lin < H; lin++)
       {
           for (col = 0; col < W; col++)
           {
               // find to where it will flow
               if (lin == 0)
                   neighb [0] = 99999;
               else
                   neighb [0] = map[lin-1][col].alt;
               if (col == 0)
                   neighb [1] = 99999;
               else
                   neighb [1] = map[lin][col-1].alt;
               if (col == (W-1))
                   neighb [2] = 99999;
               else
                   neighb [2] = map[lin][col+1].alt;
               if (lin == (H-1))
                   neighb [3] = 99999;
               else
                   neighb [3] = map[lin+1][col].alt;
               min = 0;
               if (neighb [1] < neighb[min])
                   min = 1;
               if (neighb [2] < neighb[min])
                   min = 2;
               if (neighb [3] < neighb[min])
                   min = 3;
               if (map[lin][col].alt <= neighb[min])
               {
                   // it's a sink
                   map[lin][col].sink = 1;
               }
               else
               {
                   // mark where it comes from
                   switch (min)
                   {
                       case 0: // to North, from South
                           map[lin-1][col].flows |= FLOW_SOUTH;
                           break;
                       case 1: // to West, from East
                           map[lin][col-1].flows |= FLOW_EAST;
                           break;
                       case 2: // to East, from West
                           map[lin][col+1].flows |= FLOW_WEST;
                           break;
                       case 3: // to South, from North
                           map[lin+1][col].flows |= FLOW_NORTH;
                           break;
                   }
               }

           }
       }

       // follow trees from sink to upper lands
       b = 0;
       for (lin = 0; lin < H; lin++)
       {
           for (col = 0; col < W; col++)
           {
               if (map[lin][col].sink)
               {
                   mark (lin, col, b);
                   b++;
               }
           }
       }

       // assign letters
       for (i = 0; i < 26; i++)
           letter[i] = 0;
       b = 'a';
       for (lin = 0; lin < H; lin++)
       {
           for (col = 0; col < W; col++)
           {
               if (letter [map[lin][col].basin] == 0)
                   letter [map[lin][col].basin] = b++;
           }
       }

       // print result
 printf ("Case #%d:\n", iCase);
       for (lin = 0; lin < H; lin++)
       {
           for (col = 0; col < W; col++)
           {
               i = lin*100+col;
               if (col > 0)
                   printf (" %c", letter [map[lin][col].basin]);
               else
                   printf ("%c", letter [map[lin][col].basin]);
           }
           printf ("\n");
       }
   }
}