Phân tích: King

Bài toán này tương ứng với một trò chơi tương đối ít người biết đến mang tên Slither. Trò chơi này đã được phổ biến bởi Martin Gardner trong một chuyên mục của ông viết cho tờ Scientific American. Nó không được giải quyết vào thời điểm đó, nhưng cuối cùng William Anderson đã phát triển được một lời giải. Tất nhiên, các thí sinh Code Jam thông minh hơn nhiều, vì vậy chúng tôi nghĩ rằng bài toán sẽ dễ dàng được giải quyết trong hai giờ.

Đầu tiên, tôi sẽ giải thích lời giải cho một biến thể đơn giản hơn của bài toán. Giả sử chúng ta có một bàn cờ \(3 \times 3\) với quân vua nằm ở một trong các ô góc. Bây giờ hãy phủ phần còn lại của bàn cờ bằng các quân domino kích thước \(2 \times 1\). Việc lát gạch bàn cờ này cho chúng ta thấy một chiến thuật thắng cho người chơi thứ hai. Mỗi khi người chơi thứ nhất di chuyển đến một ô của quân domino, người chơi thứ hai sẽ di chuyển đến ô còn lại của quân domino đó. Vì người chơi thứ hai luôn có thể thực hiện một nước đi sau khi người chơi thứ nhất đi, nên người chơi thứ hai có chiến thuật thắng.

Lời giải tổng quát cũng đi theo hướng tương tự: việc lát domino tương ứng với một bộ ghép lớn nhất (maximum matching). Chúng ta coi bàn cờ như một đồ thị trong đó các ô là các nút, và các ô lân cận có các cạnh nối giữa chúng. Khi đó, các quân domino tương ứng với các cạnh trong bộ ghép lớn nhất.

Lời giải được đưa ra bởi định lý sau:
"Người chơi thứ nhất có chiến thuật thắng nếu và chỉ nếu mọi bộ ghép lớn nhất đều chứa nút của quân vua".

Điều này có nghĩa là không có đường pha (alternating path) nào bắt đầu từ nút của quân vua kết thúc tại một đỉnh không nằm trong bộ ghép, bởi vì nếu nó kết thúc tại một đỉnh chưa được ghép, chúng ta có thể xây dựng một bộ ghép khác với cùng số lượng cạnh mà không sử dụng nút của quân vua. Do đó, người chơi thứ nhất luôn có thể di chuyển dọc theo một cạnh đã được ghép.

Nếu tồn tại một bộ ghép lớn nhất không chứa nút của quân vua, thì trong đồ thị này, mọi đường pha bắt đầu từ nút của quân vua đều kết thúc tại một nút đã được ghép, nếu không chúng ta có thể tăng kích thước của bộ ghép, điều này mâu thuẫn với giả định rằng bộ ghép đó là cực đại. Vì vậy, lúc này người chơi thứ hai luôn có thể di chuyển vào nút thứ hai của các cạnh trong bộ ghép. Do đó, người chơi thứ hai có chiến thuật thắng.

Đồ thị trong bài toán của chúng ta không phải là đồ thị hai phía (bipartite graph) nên chúng ta không thể sử dụng thuật toán ghép cặp hai phía thông thường. Thay vào đó, chúng ta sử dụng một giải pháp kết hợp giữa vét cạn và quy hoạch động. Giải pháp của chúng ta sẽ có độ phức tạp hàm mũ thay vì đa thức, nhưng kích thước của bài toán nhỏ nên chúng ta có thể chấp nhận được. Chúng ta đi theo từng hàng từ trái sang phải, và với mỗi ô \((i, j)\) và mỗi tập con \(S\) của \(\{0, 1, \dots, n - 1\}\), chúng ta tính toán bộ ghép tốt nhất đã có các nút sau được ghép: các nút trên đường biên hoạt động (\([i][0..j], [i-1][j+1 .. n - 1]\)) tương ứng với các số trong \(S\), và các nút đã được ghép từ trước đường biên hoạt động.

Dưới đây là mã nguồn của Derek Kisman thực hiện giải pháp này:

#include <algorithm>
#include <iostream>
using namespace std;

int gx, gy;
char g[15][15];

char memo[15][15][1<<16];
char doit(int x, int y, int b) {
  if (x == gx) {
    x = 0;
    if (++y == gy) return 0;
  }
  char& ret = memo[x][y][b];
  if (ret != -1) return ret;
  int b2 = (b<<1) & ((1<<(gx+1))-1);
  if (g[y][x] != '.') {
    ret = doit(x+1, y, b2);
  } else {
    ret = doit(x+1, y, b2+1);
    if (x && (b&1)) ret >?= 1 + doit(x+1, y, b2-2);
    if (x && (b&(1<<gx)))
      ret >?= 1 + doit(x+1, y, b2);
    if (b&(1<<(gx-1)))
      ret >?= 1 + doit(x+1, y, b2-(1<<gx));
    if (x < gx-1 && (b&(1<<(gx-2))))
      ret >?= 1 + doit(x+1, y, b2-(1<<(gx-1)));
  }
  return ret;
}

main() {
  int N, prob=1;
  for (cin >> N; N--;) {
    cin >> gy >> gx;
    int kx, ky;
    for (int y = 0; y < gy; y++)
    for (int x = 0; x < gx; x++) {
      cin >> g[y][x];
      if (g[y][x] == 'K') {kx = x; ky = y;}
    }
    memset(memo, -1, sizeof(memo));
    int m1 = doit(0, 0, 0);
    g[ky][kx] = '.';
    memset(memo, -1, sizeof(memo));
    int m2 = doit(0, 0, 0);
    cout << "Case #" << prob++
         << ": " << ((m2 > m1) ? 'A' : 'B')
         << endl;
  }
}

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