# Watersheds

My solution for the "Watersheds" task of Google Code Jam 2009 qualification round (in C language):

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <regex.h>

typedef struct map {
char basin;
int alt;
struct map *flow;
} MAP;

main() {
char str[4096], *p, curb, resb;
int T, H, W, mina;
int t, h, w;
MAP M[100][100], *m;

fgets(str, sizeof(str), stdin);
sscanf(str, "%d", &T);

for (t = 0; t < T; t++) {

fgets(str, sizeof(str), stdin);
sscanf(str, "%d %d", &H, &W);

bzero(M, sizeof(M));

for (h = 0; h < H; h++) {
fgets(str, sizeof(str), stdin);
p = str;
for (w = 0; w < W; w++) {
sscanf(p, "%d", &M[h][w].alt);
p = strchr(p, ' ') + 1;
}
}

for (h = 0; h < H; h++) {
for (w = 0; w < W; w++) {

mina = M[h][w].alt;

if (h > 0 && (M[h-1][w].alt < mina) && (M[h][w].flow == NULL || mina > M[h-1][w].alt)) { M[h][w].flow = &M[h-1][w]; mina = M[h-1][w].alt; }
if (w > 0     && (M[h][w-1].alt < mina) && (M[h][w].flow == NULL || mina > M[h][w-1].alt)) { M[h][w].flow = &M[h][w-1]; mina = M[h][w-1].alt; }
if (w < W - 1 && (M[h][w+1].alt < mina) && (M[h][w].flow == NULL || mina > M[h][w+1].alt)) { M[h][w].flow = &M[h][w+1]; mina = M[h][w+1].alt; }
if (h < H - 1 && (M[h+1][w].alt < mina) && (M[h][w].flow == NULL || mina > M[h+1][w].alt)) { M[h][w].flow = &M[h+1][w]; mina = M[h+1][w].alt; }
}
}
printf("Case #%d:\n", t + 1);
curb = 'a';
for (h = 0; h < H; h++) {
for (w = 0; w < W; w++) {
if (w) printf(" ");
if (M[h][w].basin == 0) {
m = &M[h][w];
while (m->flow != NULL) {
m = m->flow;
}
if (m->basin == 0) {
m->basin = curb++;
}
printf("%c", m->basin);
} else {
printf("%c", M[h][w].basin);
}
}
printf("\n");
}
}

return 0;
}

## 1 thought on “Watersheds”

1. Pingback: Р’РѕРґРѕСЂР°Р·РґРµР»С‹