Thuật toán loang

6a00e5536ab239883301a73dd2b493970d

Trong tuyển tập các đề thi tin học của Cuộc thi Olympic truyền thống 30 tháng 4 những năm 1999-2000 có bài này làm tôi nhớ mãi:

Cho một địa hình có dạng chữ nhật kích thước MxN. Mỗi vị trí (i, j) là một cây cột có độ cao là một số tự nhiên h[i][j] (i=1..M, j=1..N). Sau một trận mưa to, hãy tính tổng thể tích nước đọng lại trên địa hình.

Đây rõ ràng là một bài áp dụng triệt để thuật toán loang (loang dầu ăn hoặc nước đều được nhé).

Nhận xét

Một ô (i, j, k) gọi là ô trống, tức là có thể — có thể — đọng nước, nếu độ cao của cột (i, j) thấp hơn k, hay h[i][j] < k.

Việc xuất phát từ một ô trống (i, j, k), đi viếng thăm các ô trống kề mặt nó, rồi tiếp tục viếng thăm các ô trống kề mặt những ô này, cứ thế … ở cùng độ cao k, gọi là loang từ ô (i, j, k).

Khi loang từ ô (i, j, k), những ô được viếng thăm gọi là những ô loang tới được, những cột chứa những ô này gọi là những cột loang tới được.

Nếu từ một ô trống (i, j, k) mà loang ra được tới một ô ngoài biên, thì kết luận ô (i, j, k) và tất cả những ô bị loang tới, sẽ không đọng nước. Ngược lại, nếu không thể loang ra được ngoài biên, thì kết luận ô (i, j, k) và tất cả những ô bị loang tới, sẽ có đọng nước.

Tới đây, thuật toán của bài này có vẻ đơn giản là xét tất cả các ô trống, loang từ đó xem có ra biên hay không, ghi nhận tất cả những ô loang tới, và đếm số lượng là xong. Tuy nhiên, vì số lượng ô trống là rất lớn, mà mỗi lần loang rất tốn kém, nên phải có cách hạn chế số lần loang, như sau.

Nếu có một ô (i, j, k) đọng nước, và ô (i, j, k+1) không đọng nước, thì k là mực nước chính xác đọng lại ở cột (i, j), chúng ta không cần phải loang từ bất cứ ô nào thuộc cột này nữa. Tuyệt vời hơn, tất cả các cột loang tới được từ ô (i, j, k) cũng sẽ có mực nước chính xác là k (*), thật vậy:

  • Do từ ô (i, j, k) loang được tới những cột này, mà ô (i, j, k) đọng nước, suy ra những cột này cũng sẽ đọng nước ở những ô có độ cao từ k trở xuống.
  • Cũng do từ ô (i, j, k) loang được tới những cột này, thì dĩ nhiên từ ô (i, j, k+1) cũng sẽ loang được tới các cột này. Mà ô (i, j, k+1) không đọng nước, suy ra những cột này cũng sẽ không đọng nước ở những ô có độ cao từ k+1 trở lên.

Ta có thuật toán sau đây

Đặt mảng water[2..M-1][2..N-1] dùng để chứa mực nước sẽ đọng lại ở các cột. Do ô ngoài biên sẽ không thể đọng nước nên ta chỉ xét các vị trí (2..M-1, 2..N-1).

Khởi tạo toàn bộ water[i][j] = 0.

Duyệt qua lần lượt các cột (i, j) i=2..M-1, j=2..N-1:

  • Đặt k = h[i][j] + 1, kiểm tra xem ô (i, j, k) có thể đọng nước không bằng cách loang từ (i, j, k).
  • Nếu loang có kết quả (i, j, k) đọng nước thì tất cả các cột được loang (i2, j2) bao gồm cả (i, j) sẽ được cập nhật mức nước: water[i2][j2] = k – h[i2][j2]. Tăng k=k+1 và lặp lại loang.
  • Nếu loang cho thấy ô (i, j, k) không đọng nước thì dừng lặp và chuyển qua cột (i, j) tiếp theo mà có water[i][j] bằng zero, do (*).

Kết quả cuối cùng sẽ là tổng các water[i][j].

Code C

#include <stdio.h>

#define FI "WaterBlocks.inp"
#define MAX (100 + 1)

int M, N;
int h[MAX][MAX];

int water[MAX][MAX];
bool markLoang[MAX][MAX];

// dùng queue để loang theo chiều rộng (BFS)
int queueI[MAX * MAX];
int queueJ[MAX * MAX];

const int u[4] = { 0, 0, -1, 1 }; // hướng ngang
const int v[4] = { 1, -1, 0, 0 }; // hướng dọc

void readInput() {
  FILE* f = fopen(FI, "rt");
  fscanf(f, "%d %d", &M, &N);
  for (int i = 1; i <= M; ++i)
    for (int j = 1; j <= N; ++j)
      fscanf(f, "%d", &(h[i][j]));
  fclose(f);
}

bool isBorder(int i, int j) {
  return i == 1 || i == M || j == 1 || j == N;
}

bool isInside(int i, int j) {
  return i >= 1 && i <= M && j >= 1 && j <= N;
}

/**
  * return true nếu kết luận ô (i, j, k) đọng nước
  */
bool loang(int i, int j, int k) {
  for (int x = 1; x <= M; ++x)
    for (int y = 1; y <= N; ++y)
      markLoang[x][y] = false;
  markLoang[i][j] = true;
  queueI[1] = i;
  queueJ[1] = j;
  int first = 1, last = 1;
  bool result = true;
  while (first <= last) {
    i = queueI[first];
    j = queueJ[first];
    ++first;
    for (int dir = 0; dir < 4; ++dir) {
      int iNext = i + u[dir];
      int jNext = j + v[dir];
      if (!isInside(iNext, jNext)) continue;

      // ô phải trống thì mới xét
      if (h[iNext][jNext] >= k) continue;

      // ra ngoài biên, ghi nhận vô biến result
      // nhưng vẫn cứ loang tiếp vì ta cần biết
      // danh sách đầy đủ những ô bị loang tới
      if (isBorder(iNext, jNext)) result = false;

      if (markLoang[iNext][jNext]) continue;
      markLoang[iNext][jNext] = true;
      ++last;
      queueI[last] = iNext;
      queueJ[last] = jNext;
    }
  }

  return result;
}

void updateWater(int upToHeight) {
  for (int i = 2; i < M; ++i)
    for (int j = 2; j < N; ++j)
      if (markLoang[i][j])
        water[i][j] = upToHeight - h[i][j];
}

void solve() {
  for (int i = 2; i < M; ++i)
    for (int j = 2; j < N; ++j)
      water[i][j] = 0;

  for (int i = 2; i < M; ++i)
    for (int j = 2; j < N; ++j)
      if (water[i][j] == 0) {
        int k = h[i][j] + 1;
        while (loang(i, j, k)) {
          updateWater(k);
          ++k;
        }
      }
}

void writeOutput() {
  int sum = 0;
  for (int i = 2; i < M; ++i)
    for (int j = 2; j < N; ++j)
      sum += water[i][j];

  printf("%d", sum);
}

int main() {
  readInput();
  solve();
  writeOutput();
  return 0;
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s