Phân tích: Watersheds

Đối với mỗi ô, chúng ta cần xác định hố thu cuối cùng của nó. Sau đó, với mỗi nhóm các ô chia sẻ cùng một hố thu, chúng ta cần gán một nhãn duy nhất.

Dữ liệu đầu vào của bài toán này đủ nhỏ để áp dụng thuật toán mô phỏng vét cạn đơn giản. Bắt đầu với một ô và lần theo con đường mà nước sẽ đi bằng cách áp dụng lặp đi lặp lại các quy tắc dòng chảy. Dưới đây là một giải pháp khả thi bằng 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ách cài đặt và độ phức tạp

1. Tìm hố thu: Với mỗi ô \((r, c)\), ta có thể sử dụng đệ quy (có nhớ) hoặc tìm kiếm theo chiều sâu để tìm hố thu mà nó đổ về. Do quy tắc dòng chảy là duy nhất cho mỗi ô, mỗi ô sẽ dẫn đến đúng một hố thu duy nhất.
2. Đánh nhãn: Sau khi xác định được hố thu cho mọi ô, ta duyệt qua các ô theo thứ tự từ trên xuống dưới, từ trái sang phải. Nếu một ô thuộc về một lưu vực chưa được đánh nhãn, ta gán cho toàn bộ các ô chung hố thu đó chữ cái tiếp theo trong bảng chữ cái (bắt đầu từ 'a').
3. Độ phức tạp: Với mỗi bộ test, việc tìm hố thu cho mỗi ô mất \(O(H \times W)\) nếu dùng quy hoạch động hoặc \(O((H \times W)^2)\) nếu mô phỏng đơn giản. Với \(H, W \le 100\), cả hai cách đều chạy rất nhanh trong giới hạn thời gian.

Dựa trên phân tích chính thức của Google Code Jam.