Skip to content

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: Водоразделы

Leave a Reply

Your email address will not be published. Required fields are marked *