Водоразделы

Водоразделы (Watersheds) - Задача B квалификационного раунда Google Code Jam 2009.

Задача

Геологи делят поверхность земли на различные области в зависимости от того, куда стекают выпадающие осадки. Эти области называются водосборными бассейнами.

По заданной карте высот (двумерный массив), разметьте карту так, чтобы области из одного водосборного бассейна имели одну и ту же метку, следуя следующим правилам.

• Для каждой ячейки вода стекает не более, чем в одну из четырех соседних ячеек.
• Для каждой ячейки, у которой ни одна из четырех соседних ячеек не имеет меньшей высоты, вода никуда не утекает. Такая ячейка называется низиной.
• В противном случае, вода утекает из ячейки в соседнюю с минимальной высотой.
• В случае, если несколько соседних ячеек имеют одну и ту же минимальную высоту, вода течет по первому возможному направлению из следующего списка: север, запад, восток, юг.

Каждая ячейка, стекающая, прямо или косвенно, в одну и туже низину, принадлежит к одному водосборному бассейну. Каждый бассейн помечается уникальной строчной буквой таким образом, что строки карты, будучи соединенными в одну большую сверху вниз, образующаяся строка является лексикографически наименьшей из всех возможных. (В частности, бассейн самой северо-западной ячейки помечается 'a'.)

Вход

Первая строка входного файла содержит число карт, T. Затем следует T карт, каждая начинается с двух целых на строке - H и W - высоты и ширины карты, в ячейках. Следующие H строк каждая содержат строки карты, с севера на юг, каждая строка содержит W целых, с запада на восток, задающих высоты для ячеек.

Вывод

Для каждого теста, выведите 1+H строк. Первая строка должна быть в виде

Case #X:

где X - номер теста, начиная с 1. Следующие H строк должны перечислить метки бассейнов для каждой ячейки, в том же порядке, в котором ячейки подавались на вход.

Ограничения

T ≤ 100;

Малый набор данных

1 ≤ H, W ≤ 10;
0 ≤ высоты < 10. Будет не более двух бассейнов. Большой набор данных 1 ≤ H, W ≤ 100; 0 ≤ высоты < 10,000. Будет не более 26 бассейнов. Пример

5
3 3
9 6 3
5 9 6
3 5 9
1 10
0 1 2 3 4 5 6 7 8 7
2 3
7 6 7
7 6 7
5 5
1 2 3 4 5
2 9 3 9 6
3 3 0 8 7
4 9 8 9 8
5 6 7 8 9
2 13
8 8 8 8 8 8 8 8 8 8 8 8 8
8 8 8 8 8 8 8 8 8 8 8 8 8

Case #1:
a b b
a a b
a a a
Case #2:
a a a a a a a a a b
Case #3:
a a a
b b b
Case #4:
a a a a a
a a b b a
a b b b a
a b b b a
a a a a a
Case #5:
a b c d e f g h i j k l m
n o p q r s t u v w x y z

Замечание

Для теста Case #1, верхний правый и нижний левый углы являются низинами. Вода с диагонали течет к нижнему левому из-за более низкой высоты (5 по сравнению с 6).

Анализ задачи

Для каждой ячейки необходимо определить её конечную низину. Затем, для каждой группы ячеек, имеющих одну и ту же низину, приписываем уникальную метку.

Входные наборы для этой задачи достаточно маленькие для простого переборного алгоритма моделирования. Начинаем с выбранной ячейки и последовательно идем по пути, по которому течет вода согласно заданным правилам. Ниже дано одно из возможных решений на языке Python.

import sys

def ReadInts():
  return list(map(int, sys.stdin.readline().strip().split(" ")))

def Cross(a, b):
  for i in a:
    for j in b:
      yield (i, j)

def Neighbours(ui, uj, m, n):
  if ui - 1 >= 0: yield (ui - 1, uj)
  if uj - 1 >= 0: yield (ui, uj - 1)
  if uj + 1 < n: yield (ui, uj + 1)
  if ui + 1 < m: yield (ui + 1, uj)

N = ReadInts()[0]
for prob in xrange(1, N + 1):
  # Read the map
  (m, n) = ReadInts()
  maze = [ReadInts() for _ in xrange(m)]
  answer = [["" for _ in xrange(n)] for _ in xrange(m)]

  # The map from sinks to labels.
  label = {}
  next_label = 'a'

  # Brute force each cell.
  for (ui, uj) in Cross(xrange(m), xrange(n)):
    (i, j) = (-1, -1)
    (nexti, nextj) = (ui, uj)
    while (i, j) != (nexti, nextj):
      (i, j) = (nexti, nextj)
      for (vi, vj) in Neighbours(i, j, m, n):
        if maze[vi][vj] < maze[nexti][nextj]:
          (nexti, nextj) = (vi, vj)

    # Cell (ui, uj) drains to (i, j).
    if (i, j) not in label:
      label[(i, j)] = next_label
      next_label = chr(ord(next_label) + 1)
    answer[ui][uj] = label[(i, j)]

  # Output the labels.
  print "Case #%d:" % prob
  for i in xrange(m):
    print " ".join(answer[i])

Решение на языке C: blog.dataparksearch.org/180.