Phân tích

Để thuận tiện cho việc thảo luận, chúng ta ký hiệu \(c_{i,j}\) là số nhập vào tại vị trí \((i,j)\), tức là số lượng mìn trong hình vuông \(3 \times 3\) tâm tại \((i,j)\). Trong lời giải dưới đây, chúng ta sẽ thấy rằng bất kỳ ô vuông nào có thể giải được đều phải có một đáp án duy nhất cho số lượng mìn ở hàng giữa.

(1) Số lượng mìn trong 3 hàng bất kỳ và 3K cột

Trong hình dưới đây, hãy cộng các giá trị \(c_{i,j}\) tại các vị trí được đánh dấu sao.

(2) Số lượng mìn trong 3 hàng bất kỳ và C cột

Nếu \(C\) không phải là bội số của 3, dựa trên \(C \pmod 3\), ta sử dụng một hoặc hai hình vuông ở biên.

Tóm lại, để có được số lượng mìn trong ba hàng liên tiếp bất kỳ, chúng ta nhìn vào hàng giữa, bắt đầu từ ô thứ nhất hoặc thứ hai và đánh dấu mỗi ô thứ 3. Gọi hàng giữa là hàng thứ \(a\). Chúng ta ký hiệu tổng này là \(F_a\).

Cũng lưu ý rằng với cùng một phương pháp, \(F_0\) cho biết số lượng mìn trong hai hàng đầu tiên và \(F_{R-1}\) cho biết số lượng mìn trong hai hàng cuối cùng.

(3) Số lượng mìn trong toàn bộ bảng

Tương tự, dựa trên \(R \pmod 3\), bắt đầu từ \(a = 0\) hoặc \(1\) và cộng các \(F_a\) cho mỗi số thứ 3.

(4) Số lượng mìn trong 3K hoặc 3K+2 hàng đầu tiên

Chúng ta bỏ qua hình minh họa ở đây vì nó tương tự như các hình trên. Chúng ta có thể nhóm 2 hàng đầu tiên lại với nhau, hoặc 3 hàng đầu tiên. Bằng tính đối xứng, chúng ta cũng có thể lấy được số lượng mìn trong \(3K\) hoặc \(3K+2\) hàng cuối cùng.

(5) Số lượng mìn ở hàng giữa

Gọi \(h = (R - 1) / 2\). Có \(h\) hàng phía trên hàng giữa, cũng như \(h\) hàng phía dưới.

• Nếu \(h \pmod 3\) là 0 hoặc 2, chúng ta có thể lấy tổng của \(2h\) hàng đó từ bước (4) và trừ nó khỏi tổng số mìn từ bước (3).
• Nếu \(h \pmod 3\) là 1, chúng ta có thể lấy tổng của \(h+1\) hàng đầu tiên từ bước (4), cũng như tổng của \(h+1\) hàng cuối cùng. Chỉ có hàng trung tâm được tính hai lần, vì vậy chúng ta có thể lấy tổng này trừ đi tổng số mìn từ bước (3).

Cách cài đặt

Dưới đây là mã nguồn tham khảo từ ban giám khảo:

int T, R, C;
int c[100][100];

int SumRowsCentered(int a) { // F(a) as in the discussion.
  int r=0;
  for(int i=(C%3)?0:1; i<C; i+=3) r+=c[a][i];
  return r;
}

int play() {
  int i;
  // Get the total.
  int total=0;
  for(i=(R%3)?0:1; i<R; i+=3) total+=SumRowsCentered(i);
  // Get the answer.
  int h=(R-1)/2; int S=0;
  if (h%3==1) {
    for(i=h-1;i>=0;i-=3) S+=SumRowsCentered(i);
    for(i=h+1;i<R;i+=3) S+=SumRowsCentered(i);
    return S-total;
  } else {
    for(i=h-2;i>=0;i-=3) S+=SumRowsCentered(i);
    for(i=h+2;i<R;i+=3) S+=SumRowsCentered(i);
    return total-S;
  }
  return 0;
}

int main() {
  int i,j,k;
  cin>>T;
  for (i=1; i<=T; i++) {
    cin>>R>>C;
    for(j=0;j<R;j++) for (k=0;k<C;k++) cin>>c[j][k];
    cout<<"Case #"<<i<<": "<<play()<<endl;
  }
  return 0;
}

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