Phân tích: Descending in the Dark

Thách thức chính trong bài toán này là xác định xem một hang động có may mắn hay không. Tập hợp tất cả các trạng thái có thể là rất lớn, vì vậy việc tìm kiếm vét cạn trên tất cả các kế hoạch đơn giản là sẽ không hiệu quả. May mắn thay, có một quan sát mà chúng ta có thể sử dụng để đơn giản hóa đáng kể nhiệm vụ này.

Loại bỏ việc quay lui (Backtracking)

Cố định một hang động C, và nhớ lại rằng \(S_C\) ký hiệu tập hợp các ô mà từ đó có thể đến được C. Chúng ta sẽ xây dựng kế hoạch của mình từng chỉ dẫn một.

Gọi X là tập hợp các ô mà bạn có thể đang đứng nếu bạn bắt đầu từ \(S_C\) và tuân theo kế hoạch cho đến thời điểm hiện tại. Nếu X chứa một ô không nằm trong \(S_C\), chúng ta biết kế hoạch đó không thể hoạt động cho mọi vị trí bắt đầu. Ngược lại, chúng ta có thể chắc chắn 100% rằng kế hoạch cho đến nay là ổn! Điều này là do tập hợp các ô khả thi mà chúng ta đang đứng hoặc giữ nguyên hoặc trở nên nhỏ hơn một cách nghiêm ngặt. Đặc biệt, nếu có một kế hoạch hoạt động từ vị trí bắt đầu, chúng ta có thể nối nó vào những gì chúng ta đã làm cho đến nay, và nó vẫn sẽ hoạt động.

Vậy điều này có nghĩa là gì? Miễn là chúng ta không thực hiện một bước di chuyển nào thêm một ô không thuộc \(S_C\) vào tập hợp các ô khả thi X, chúng ta có thể tiến hành bước di chuyển đó, và vẫn có khả năng hoàn thành kế hoạch. Cụ thể, chúng ta luôn có thể di chuyển sang trái và sang phải bất cứ khi nào chúng ta muốn, vì di chuyển sang trái hoặc phải không bao giờ có thể đưa bạn ra khỏi \(S_C\).

Tất cả những gì bạn cần là Xuống!

Ngay cả với quan sát trước đó, chúng ta vẫn còn việc phải làm. Bây giờ chúng ta biết tất cả các bước di chuyển có thể thực hiện an toàn, nhưng không gian trạng thái vẫn còn khổng lồ. Chúng ta không thể tìm bất kỳ bước di chuyển nào; chúng ta cần một bước tạo ra tiến triển.

Đây là lúc tính chất bạn không thể leo lên núi trở nên quan trọng. Giả sử bạn có thể thêm một bước di chuyển Xuống (Down) vào kế hoạch, thỏa mãn hai tính chất sau:

• Có ít nhất một vị trí trong X mà từ đó bạn thực sự có thể di chuyển xuống. (Nếu không, bước di chuyển Xuống sẽ không bao giờ làm gì cả, và do đó là vô dụng!)
• Không có vị trí nào trong X mà từ đó một bước di chuyển xuống sẽ đưa bạn ra ngoài \(S_C\).

Nếu bạn thêm bước di chuyển Xuống này vào kế hoạch, thì tổng độ cao của tất cả các ô trong X sẽ giảm xuống, và nó không bao giờ có thể tăng lên nữa, vì bạn không bao giờ có thể leo núi!

Vì tổng độ cao là một số nguyên dương, cuối cùng bạn sẽ phải ngừng thực hiện các bước di chuyển Xuống. Tại thời điểm đó, bạn bị kẹt trong một hoặc nhiều khoảng ngang. Nếu chỉ có một khoảng và nó chứa hang động, kế hoạch có thể được hoàn thành thành công. Ngược lại, bạn đã thất bại! Và hãy nhớ rằng, vì tập hợp các ô này là tập con của những gì bạn đã bắt đầu, nên thực tế bạn đã thất bại ngay từ đầu.

Bạn có thể đi xuống không?

Chỉ còn một câu hỏi: cho một tập hợp các vị trí X có thể đạt được từ lúc bắt đầu, bạn có thể đưa ra một kế hoạch hợp lệ bao gồm ít nhất một bước di chuyển Xuống không?

X phải được chứa trong một tập hợp các khoảng ngang, được giới hạn bởi các ô không thể đi qua ở bên trái và bên phải. Vì luôn an toàn khi di chuyển sang trái và phải, chúng ta có thể tiếp tục di chuyển sang trái cho đến khi X thực sự chỉ là ô ngoài cùng bên trái trong mỗi khoảng này. Nếu chúng ta không thể tạo ra tiến triển từ tình huống đó, chúng ta đã chứng minh được rằng mình bị lạc.

Khi chúng ta thực hiện các bước di chuyển trái và phải từ đó, vị trí của chúng ta trong mỗi khoảng có thể thay đổi. Tuy nhiên, lưu ý rằng nếu hai khoảng có cùng độ dài, vị trí ngang tương đối của chúng ta trong chúng sẽ luôn giống nhau. Do đó, hãy định nghĩa \(x_j\) là vị trí ngang tương đối của chúng ta trong tất cả các khoảng có độ dài \(j\). (Cụ thể, \(x_j = 0\) nếu chúng ta ở vị trí ngoài cùng bên trái, và \(x_j = j - 1\) nếu chúng ta ở vị trí ngoài cùng bên phải.)

Bổ đề: Có thể đạt được vị trí \((x_1, x_2, ...)\) bằng cách di chuyển trái và phải nếu và chỉ nếu \(x_i \le x_j \le x_i + j - i\) với mọi \(i < j\).

Chứng minh: Đầu tiên chúng ta chỉ ra \(x_i \le x_j\). Điều này đúng lúc ban đầu. Nếu nó thất bại sau một chuỗi các bước di chuyển, đó là vì \(x_i\) và \(x_j\) bằng nhau, và sau đó hoặc là:

• Chúng ta di chuyển sang trái, và chỉ \(x_j\) có thể di chuyển.
• Chúng ta di chuyển sang phải, và chỉ \(x_i\) có thể di chuyển.

Tuy nhiên, cả hai kịch bản này đều không thể xảy ra. Do đó, \(x_i\) thực sự tối đa là \(x_j\), hay nói cách khác, khoảng cách từ \(x_i\) đến tường bên trái không lớn hơn khoảng cách từ \(x_j\) đến tường bên trái. Lập luận tương tự có thể được áp dụng cho tường bên phải, điều này cho chúng ta nửa còn lại của bất đẳng thức: \(x_j \le x_i + j - i\).

Ngược lại, bất kỳ tập hợp các vị trí nào với \(x_i \le x_j \le x_i + j - i\) thực sự có thể đạt được thông qua thuật toán sau:

• Bắt đầu với mỗi \(x_i = 0\).
• Lặp từ \(i\) = độ dài khoảng lớn nhất xuống 2.
• Di chuyển \(i - 2 + x_i - x_{i-1}\) lần sang phải, và sau đó \(i - 2\) lần sang trái.

Hãy tự mình thử và bạn sẽ thấy tại sao nó hoạt động!

Đến đây chúng ta về cơ bản đã xong. Chúng ta cần xác định xem có tập hợp các vị trí \(\{x_i\}\) nào có thể đạt được mà từ đó việc di chuyển xuống là an toàn hay không. Khi đã đi đến bước này, bạn có thể kết thúc nó bằng quy hoạch động. Dưới đây là một số mã giả xác định xem có tồn tại một tập hợp các vị trí mà từ đó có thể di chuyển xuống và tạo ra tiến triển hay không:

old_safety = [SAFE] * (n+1)
for length in {n, n-1, ..., 1}:
  for i in [0, length-1]:
    pos_safety[i] = best(old_safety[i], old_safety[i+1])
    if moving down leaves SC:
      pos_safety[i] = UNSAFE
    elif moving down is legal and pos_safety[i] == SAFE:
      pos_safety[i] = SAFE_WITH_PROGRESS
  old_safety = pos_safety
return (pos_safety[0] == SAFE_WITH_PROGRESS)

Đây là một điểm khởi đầu tốt, nhưng bạn vẫn phải điều chỉnh nó để thực sự ghi lại \(x_i\) phù hợp cho mọi \(i\).

Tổng hợp lại, chúng ta lặp lại việc sử dụng thuật toán trên để xem liệu có thể thực hiện một bước di chuyển xuống hay không. Nếu có, chúng ta thực hiện nó và lặp lại. Nếu không, chúng ta dừng lại. Nếu khoảng duy nhất còn lại là khoảng chứa hang động, thì hang động đó là may mắn. Ngược lại, nó không may mắn!

Dưới đây là mã nguồn tham khảo đầy đủ bằng Java (bởi Petr Mitrichev):

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Dark {
 static class Segment {
  int len;
  long goodExitMask;
  long badExitMask;
 }

 public static void main(String[] args) throws IOException {
  BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
  int numTests = Integer.parseInt(reader.readLine());
  for (int testId = 0; testId < numTests; ++testId) {
   String[] parts = reader.readLine().split(" ", -1);
   if (parts.length != 2) throw new RuntimeException();
   int rows = Integer.parseInt(parts[0]);
   int cols = Integer.parseInt(parts[1]);
   String[] field = new String[rows];
   for (int r = 0; r < rows; ++r) {
    field[r] = reader.readLine();
    if (field[r].length() != cols) throw new RuntimeException();
   }
   System.out.println("Case #" + (testId + 1) + ":");
   for (char caveId = '0'; caveId <= '9'; ++caveId) {
    int cr = -1;
    int cc = -1;
    for (int r = 0; r < rows; ++r)
     for (int c = 0; c < cols; ++c)
      if (field[r].charAt(c) == caveId) {
       cr = r;
       cc = c;
      }
    if (cr < 0) continue;
    boolean[][] reach = new boolean[rows][cols];
    reach[cr][cc] = true;
    int nc = 1;
    while (true) {
     boolean updated = false;
     for (int r = 0; r < rows; ++r)
      for (int c = 0; c < cols; ++c)
       if (reach[r][c]) {
        if (r > 0 && field[r - 1].charAt(c) != '#' && !reach[r - 1][c]) {
         reach[r - 1][c] = true;
         ++nc;
         updated = true;
        }
        if (c > 0 && field[r].charAt(c - 1) != '#' && !reach[r][c - 1]) {
         reach[r][c - 1] = true;
         ++nc;
         updated = true;
        }
        if (c + 1 < cols && field[r].charAt(c + 1) != '#' && !reach[r][c + 1]) {
         reach[r][c + 1] = true;
         ++nc;
         updated = true;
        }
       }
     if (!updated) break;
    }
    List<Segment> segments = new ArrayList<Segment>();
    for (int r = 0; r <= cr; ++r)
     for (int c = 0; c < cols; ++c)
      if (reach[r][c] && (c == 0 || !reach[r][c - 1])) {
       int c1 = c;
       while (reach[r][c1 + 1]) ++c1;
       Segment s = new Segment();
       s.len = c1 - c + 1;
       for (int pos = c; pos <= c1; ++pos) {
        if (r + 1 < rows && field[r + 1].charAt(pos) != '#') {
         if (reach[r + 1][pos])
          s.goodExitMask |= 1L << (pos - c);
         else
          s.badExitMask |= 1L << (pos - c);
        }
       }
       segments.add(s);
      }
    while (true) {
     int maxLen = 0;
     for (Segment s : segments)
      maxLen = Math.max(maxLen, s.len);
     long[] badByLen = new long[maxLen + 1];
     for (Segment s : segments) {
      badByLen[s.len] |= s.badExitMask;
     }
     long[] possible = new long[maxLen + 1];
     possible[1] = 1;
     for (int len = 1; len <= maxLen; ++len) {
      possible[len] &= ~badByLen[len];
      if (len < maxLen) {
       possible[len + 1] = possible[len] | (possible[len] << 1);
      }
     }
     for (int len = maxLen; len > 1; --len) {
      possible[len - 1] &= possible[len] | (possible[len] >> 1);
     }
     List<Segment> remaining = new ArrayList<Segment>();
     for (Segment s : segments)
      if ((s.goodExitMask & possible[s.len]) == 0) {
       remaining.add(s);
      }
     if (remaining.size() == segments.size()) break;
     segments = remaining;
    }
    System.out.println(caveId + ": " + nc + " " + (segments.size() == 1 ? "Lucky" : "Unlucky"));

   }
  }
 }
}

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