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.
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.
- 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
//
// 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");
}
}
}
Nenhum comentário:
Postar um comentário