Phân tích

Một giải pháp cho bài toán này là thử đặt các ô màu đỏ theo mọi cách có thể lên các ô màu xanh và xem liệu có ít nhất một khả năng dẫn đến việc tất cả các ô màu xanh đều được che phủ hay không. Tuy nhiên, cách này sẽ không kịp thời gian vì có quá nhiều tổ hợp để thử.

Để tối ưu hóa giải pháp, bạn phải quan sát thấy rằng nếu tồn tại một lời giải, thì ô màu xanh nằm ở trên cùng nhất và bên trái nhất trong lưới (tức là ô nằm bên trái nhất trong số tất cả các ô màu xanh thuộc hàng trên cùng có chứa ô màu xanh) phải được che bởi góc trên bên trái của một ô màu đỏ nào đó. Điều này là do các ô ở bên trái và bên trên nó đều là màu trắng (hoặc không tồn tại), vì vậy ô màu đỏ che ô màu xanh của chúng ta không thể mở rộng sang trái hoặc lên trên nó. Dựa trên quan sát này, chúng ta có thể giải quyết bài toán một cách tham lam bằng cách đặt một ô màu đỏ đè lên ô màu xanh trên cùng nhất, bên trái nhất theo cách duy nhất có thể. Nếu đối với một ô màu xanh nào đó mà không thể che nó theo cách này (vì ô màu đỏ sẽ đè lên các ô màu trắng hoặc nằm ngoài bức tranh), thì việc che toàn bộ bảng là không thể.

Lưu ý rằng vì chúng ta luôn chắc chắn rằng bất kỳ ô màu đỏ nào chúng ta đặt xuống đều là chính xác (nếu tồn tại lời giải), chúng ta có thể sửa đổi bảng trực tiếp, và do đó vừa kiểm tra sự tồn tại của lời giải vừa lấy được kết quả cùng một lúc.

Cách cài đặt

Dưới đây là một hàm C++ để che tất cả các ô màu xanh trong lưới và trả về việc điều đó có khả thi hay không:

bool CoverTiles(vector<string>& grid) {
  const int m = (int)grid.size(), n = (int)grid[0].size();
  for (int i = 0; i < m; ++i)
    for (int j = 0; j < n; ++j)
      if (grid[i][j] == '#') {
        for (int di = 0; di < 2; ++di)
          for (int dj = 0; dj < 2; ++dj)
            if (i + di < m && j + dj < n &&
                grid[i + di][j + dj] == '#')
              grid[i + di][j + dj] = "/\\"[(di + dj) % 2];
            else
              return false;
      }
  return true;
}

Sự thật thú vị: Giải pháp không thay đổi nếu chúng ta bỏ yêu cầu các ô màu đỏ phải che các khối vuông \(2 \times 2\) của các ô màu xanh - nó vẫn đúng nếu chúng ta cho phép xoay và định vị tùy ý các ô màu đỏ; điều kiện duy nhất quan trọng là các ô màu đỏ chỉ nằm trên các ô màu xanh (không chồng chéo, không lòi ra ngoài tranh hoặc nằm trên các ô màu trắng) và tất cả các ô màu xanh cuối cùng đều được che hết.

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