VOJ - BCHESS

Source: BCHESS
Tags: Dynamic Programming

Problem:
Bàn cờ là một hình vuông có các ô đen trắng xen kẽ.
Bàn cờ loại 1 là bàn cờ có 2 góc đối diện có màu giống nhau, 2 góc kề có màu khác nhau.
Bàn cờ loại 2 là bàn cờ có 4 góc cùng màu đen (1 ô đen được coi là bàn cờ loại 2).
Bàn cờ loại 3 là bàn cờ có 4 góc cùng màu trắng (1 ô trắng được coi là bàn cờ loại 3).

Cho một bảng kích thước N × N gồm các ô mang giá trị 0 (màu trắng) và 1 (màu đen). Gọi S[A] là độ dài cạnh lớn nhất của bàn cờ loại A có thể tìm được trên bảng và T[A] là số bàn cờ loại A có cùng độ dài S[A]. Tìm S[i], T[i] với i = 1..3. 

Ví dụ:
Input: 

5

00101

11010

00101

01010

11101

Output:

4 1

3 3

3 2

Explanation:

Các bàn cờ loại 1: (1, 2) → (4, 5)

Các bàn cờ loại 2: (1, 3) → (3, 5); (2, 2) → (4, 4); (3, 3) → (5, 5)

Các bàn cờ loại 3: (1, 2) → (3, 4); (2, 3) → (4, 5)

Solution:

Đầu tiên nhận xét được rằng, bàn cờ loại 1 luôn có độ dài cạnh chẵn còn bàn cờ loại 2 và 3 luôn có độ dài cạnh lẻ.

Gọi B[i][j] là độ dài cạnh lớn nhất của bàn cờ có ô góc phải dưới là ô đen, W[i][j] là độ dài cạnh lớn nhất của bàn cờ có ô góc phải dưới là ô trắng.

- Nếu A[i][j] = 1 thì W[i][j] = 0, nếu A[i][j] = 0 thì B[i][j] = 0.

- Nếu bàn cờ có ô góc phải dưới (i, j) là ô đen thì ô (i - 1, j - 1) cũng phải màu đen và là ô góc phải dưới của bàn cờ tương ứng. Đồng thời ô (i - 1, j) và ô (i, j - 1) phải là ô trắng và là ô góc phải dưới của bàn cờ tương ứng. Vậy có công thức B[i][j] = min(B[i - 1][j - 1], W[i - 1][j], W[i][j - 1]) + 1. (cộng 1 vì lúc này ta đã mở rộng cạnh bàn cờ thêm 1 ô). Tương tự với W[i][j].

Cứ mỗi lần tính ra giá trị B[i][j], W[i][j] ta cập nhật lại các đáp án.

Code:

#include <iostream>

using namespace std;

int n, b[2015][2015], w[2015][2015], s[3], t[3];

void update(int val, int &ans, int &cnt) {

if (val > ans) ans = val, cnt = 1;

else cnt += val == ans;

}

int main() {

cin >> n;

for (int i = 1; i <= n; i++)

for (int j = 1; j <= n; j++) {

    char c; cin >> c;

if (c == '1')

w[i][j] = 0,

b[i][j] = min(b[i - 1][j - 1], min(w[i - 1][j], w[i][j - 1])) + 1,

update(b[i][j] - (b[i][j] & 1), s[0], t[0]),

update(b[i][j] - !(b[i][j] & 1), s[1], t[1]);

else 

b[i][j] = 0,

w[i][j] = min(w[i - 1][j - 1], min(b[i - 1][j], b[i][j - 1])) + 1,

update(w[i][j] - (w[i][j] & 1), s[0], t[0]),

update(w[i][j] - !(w[i][j] & 1), s[2], t[2]);

        }

for (int i = 0; i < 3; i++)

    cout << s[i] << ' ' << t[i] << '\n';

}