P1169 "chessboard making"

1. subject

Topic link ：P1169「 Chessboard making 」 .

Title Description

Chess is one of the oldest games in the world , And Chinese go 、 Chess and Japanese Jiangqi share a great reputation . It is said that chess originated from the idea of the book of changes , The chessboard is a 8 \times 8 The size of the black and white square , Corresponding to the eight hundred and sixty-four hexagrams , Black and white correspond to Yin and Yang .

And our hero is little Q, It's a chess enthusiast . As a top player , He is no longer satisfied with the ordinary chessboard and rules , So he was with his good friend W Decided to enlarge the board to fit their new rules .

Small Q I found one by N \times M A rectangular piece of paper made up of a square lattice , Each grid is painted in either black or white . Small Q I want to cut part of this paper as a new chessboard , Of course , He wants the board to be as big as possible .

But small Q It has not been decided whether to find a square chessboard or a rectangular chessboard （ Of course , No matter what kind of , The chessboard has to be black and white , That is, the adjacent grids have different colors ）, So he hopes to find the largest square chessboard area and the largest rectangular chessboard area , To decide which is better .

So small Q I found you who will take part in the national informatics competition , Can you help him ？

Input format

Contains two integers N and M, They represent the length and width of a rectangular piece of paper . Next N The line contains a N \ \times M Of 01 matrix , Indicates the color of this rectangular piece of paper （0 Said the white ,1 According to black ）.

Output format

It contains two lines , Each line contains an integer . The first line is the area of the largest square chessboard that can be found , The second line is the area of the largest rectangular chessboard that can be found （ Note that squares and rectangles can intersect or contain ）.

I/o sample

Input #1

3 3
1 0 1
0 1 0
1 0 0

Output #1

4
6

explain / Tips

about 20\% The data of ,N, M ≤ 80 .

about 40\% The data of ,N, M ≤ 400 .

about 100\% The data of ,N, M ≤ 2000 .

2. Answer key

analysis

Monotonic stack （ Method 1 ）

At a glance, the online boss can see that the row number of black and white blocks on the chessboard is and is only one of the following two cases ：

• The row and column numbers of black blocks have the same parity , White blocks are different .
• The row and column numbers of white blocks have the same parity , Different black blocks .

So we can scan the whole board twice , For the first time, assume that the chessboard meeting the requirements is the first case , be ：

• Black and white blocks conforming to the first case are marked as 1 .
• Black and white blocks that do not conform to the first condition are marked as 0 . So we get the maximum inner rectangle of the chessboard that meets the requirements in the first case / The square area is the largest inner rectangle of the rectangle corresponding to the two-dimensional marker array / Square area . Convert to follow P4147「 Jade toad Palace 」 Basically the same problem , Monotonous stack is easy to solve .

The second assumption is that the chessboard that meets the requirements is the second case , be ：

• Black and white blocks conforming to the second case are marked as 1 .
• Black and white blocks that do not conform to the second condition are marked as 0 . Then we get the maximum inner rectangle of the chessboard that meets the requirements in the second case / The square area is the largest inner rectangle of the rectangle corresponding to the two-dimensional marker array / Square area . Convert to follow P4147「 Jade toad Palace 」 Basically the same problem , Monotonous stack is easy to solve .

The final answer is the maximum inner rectangle of the chessboard that meets one of the above two conditions / The maximum value of the square .

Monotonic stack （ Method 2 ）

For me of konjaku , Without the insight of the big guys . That's what I think ： similar P4147「 Jade toad Palace 」 equally , For the whole board a[i][j],i \in [0,n), j \in [0,m) Scan line by line , Record point (i,j) The corresponding maximum column height that meets the requirements b[i][j], That is, from point (i,j) The length of alternating black and white blocks that are continuous upward ：

Then the same idea of monotone stack , Treat each row separately . The difference is , Processing point (i,j) when ：

• If a[i][j-1] \ne a[i][j] ] when , Explain that for i All right , Column j Meet to list j-1 The chessboard formed at the end requires , At this point, according to the ordinary monotone stack, the b[i][j] Just press the stack .
• If a[i][j-1] = a[i][j] when , Explain that for i All right , Column j Not satisfied with the column j−1 The chessboard formed at the end requires , At this time, the chessboard has been split , namely j All columns in the future cannot be associated with j The front columns form a reasonable chessboard , So the stack is empty , And modify the rectangular boundary at the top of the stack to j−1 after , then b[i][j] Pressing stack .

The whole is the idea of monotonous stack , Only the stack pressing operation has been modified .

Suspension method

This problem can also be solved by the hanging line method . The hanging line method mainly involves three arrays ：

• height[i][j] ： Used to denote points (i,j) The highest height that can be reached upwards .
• left[i][j]： Used to denote points (i,j) Maximum left boundary that can be extended to the left .
• right[i][j]： Used to denote points (i,j) The smallest right boundary that can be extended to the right .

The dangling method first needs to initialize these three arrays ：

\begin{array}{c} height[i][j] = 1 \\ left[i][j] = right[i][j] = 1 \end{array}

Then, each point is processed according to the row, and the maximum left boundary that can be reached in that row left[i][j] And the minimum right boundary ：

\begin{array}{c} left[i][j] = left[i][j-1], \quad \text{ If you order } (i,j) \text{ Sum point } (i,j-1) \text{ There were no obstacles before } \\ right[i][j] = right[i][j+1], \quad \text{ If you order } (i,j) \text{ Sum point } (i,j+1) \text{ There are no obstacles between them } \end{array}

Then process points by column (i,j) The highest height that can be reached upwards , At the same time, the maximum left boundary and the minimum right boundary of the maximum inner rectangle with this height are updated ：

\begin{array}{c} height[i][j] = h[i-1][j] + 1, \quad \text{ If you order } (i,j) \text{ Sum point } (i-1,j) \text{ There are no obstacles between them } \\ left[i][j] = \max (left[i][j], left[i-1][j]) \\ right[i][j] = \min (right[i][j], right[i-1][j]) \end{array} ​

Last , Calculate to point (i,j) Up （ The highest priority ） Left to right （ Priority level is second ） The maximum rectangular area that can be formed , And record the answers that meet the conditions .

Code

Monotonic stack （ Method 1 ）

#include <bits/stdc++.h>
#define MAXN 2005
using namespace std;

int ans1 = 0;
int ans2 = 0;

struct DC{
    int i;
    int v;
    DC(): i(0),v(0) {}
    DC(int _i, int _v): i(_i),v(_v) {}
};

void maxRectangle(int *b, int m) {
    DC dc[MAXN];
    int depth = 0;
    dc[depth] = DC{-1,-1};
    for(int j = 0; j < m; ++j) {
        int sdepth = depth;
        while(depth && b[j] <= dc[depth].v) {
            int c = dc[sdepth].i - dc[depth-1].i;
            int d = dc[depth].v;
            ans1 = max(ans1, min(c*c, d*d));
            ans2 = max(ans2, c*d);
            --depth;
        }
        dc[++depth] = DC{j,b[j]};
    }
    int sdepth = depth;
    while(depth) {
        int c = dc[sdepth].i - dc[depth-1].i;
        int d = dc[depth].v;
        ans1 = max(ans1, min(c*c, d*d));
        ans2 = max(ans2, c*d);
        --depth;
    }
}

int main()
{
    int n, m;
    static int a[MAXN][MAXN], b[MAXN][MAXN], c[MAXN][MAXN];
    scanf("%d%d", &n, &m);
    for(int i = 0; i < n; ++i) {
        for(int j = 0; j < m; ++j) {
            scanf("%d", &a[i][j]);
        }
    }
    for(int i = 0; i < n; ++i) {
        for(int j = 0; j < m; ++j) {
            if((!((i&1)^(j&1)) && a[i][j]) || (((i&1)^(j&1)) && !a[i][j])){
                b[i][j] = 1;
            } else {
                b[i][j] = 0;
            }
        }
    }
    for(int j = 0; j < m; ++j) {
        c[0][j] = b[0][j];
    }
    for(int i = 1; i < n; ++i) {
        for(int j = 0; j < m; ++j) {
            if(b[i][j]) {
                c[i][j] = c[i-1][j] + 1;
            } else {
                c[i][j] = 0;
            }
        }
    }
    for(int i = 0; i < n; ++i) {
        maxRectangle(c[i], m);
    }
    for(int i = 0; i < n; ++i) {
        for(int j = 0; j < m; ++j) {
            if((!((i&1)^(j&1)) && a[i][j]) || (((i&1)^(j&1)) && !a[i][j])){
                b[i][j] = 0;
            } else {
                b[i][j] = 1;
            }
        }
    }
    for(int j = 0; j < m; ++j) {
        c[0][j] = b[0][j];
    }
    for(int i = 1; i < n; ++i) {
        for(int j = 0; j < m; ++j) {
            if(b[i][j]) {
                c[i][j] = c[i-1][j] + 1;
            } else {
                c[i][j] = 0;
            }
        }
    }
    for(int i = 0; i < n; ++i) {
        maxRectangle(c[i], m);
    }
    printf("%d\n%d\n", ans1, ans2);
    return 0;
}

Monotonic stack （ Method 2 ）

#include <bits/stdc++.h>
#define MAXN 2005
using namespace std;

int ans1 = 0;
int ans2 = 0;

struct DC{
    int i;
    int v;
    DC(): i(0),v(0) {}
    DC(int _i, int _v): i(_i),v(_v) {}
};

void maxRectangle(int a[], int b[], int m) {
    int depth = 0;
    DC stack[MAXN];
    stack[depth] = DC{-1,-1};
    stack[++depth] = DC{0,b[0]};
    for(int j = 1; j < m; ++j) {
        int sdepth = depth;
        if(a[j-1] != a[j]) {
            while(depth && stack[depth].v >= b[j]) {
                int c = stack[sdepth].i - stack[depth-1].i;
                int d = stack[depth].v;
                ans1 = max(ans1, min(c*c, d*d));
                ans2 = max(ans2, c*d);
                --depth;
            }
        } else {
            while(depth) {
                int c = stack[sdepth].i - stack[depth-1].i;
                int d = stack[depth].v;
                ans1 = max(ans1, min(c*c, d*d));
                ans2 = max(ans2, c*d);
                --depth;
            }
            stack[0].i = j - 1;
        }
        stack[++depth] = DC{j,b[j]};
    }
    int sdepth = depth;
    while(depth) {
        int c = stack[sdepth].i - stack[depth-1].i;
        int d = stack[depth].v;
        ans1 = max(ans1, min(c*c, d*d));
        ans2 = max(ans2, c*d);
        --depth;
    }
}

int main()
{
    int n, m;
    static int a[MAXN][MAXN], b[MAXN][MAXN];
    scanf("%d%d", &n, &m);
    for(int i = 0; i < n; ++i) {
        for(int j = 0; j < m; ++j) {
            scanf("%d", &a[i][j]);
        }
    }
    for(int j = 0; j < m; ++j) {
        b[0][j] = 1;
    }
    for(int i = 1; i < n; ++i) {
        for(int j = 0; j < m; ++j) {
            if(a[i][j] != a[i-1][j]) {
                b[i][j] = b[i-1][j] + 1;
            } else {
                b[i][j] = 1;
            }
        }
    }
    for(int i = 0; i < n; ++i) {
        maxRectangle(a[i], b[i], m);
    }
    printf("%d\n%d\n", ans1, ans2);
    return 0;
}

Suspension method

#include <bits/stdc++.h>
#define MAXN 2005
using namespace std;

int main()
{
    int n, m;
    static int a[MAXN][MAXN], l[MAXN][MAXN], r[MAXN][MAXN], h[MAXN][MAXN];
    scanf("%d%d", &n, &m);
    for(int i = 0; i < n; ++i) {
        for(int j = 0; j < m; ++j) {
            scanf("%d", &a[i][j]);
        }
    }
    for(int i = 0; i < n; ++i) {
        for(int j = 0; j < m; ++j) {
            l[i][j] = j;
            r[i][j] = j;
            h[i][j] = 1;
        }
    }
    //  Processing every line 
    for(int i = 0; i < n; ++i) {
        for(int j = 1; j < m; ++j) {
            if(a[i][j] != a[i][j-1]) {
                l[i][j] = l[i][j-1];
            }
        }
        for(int j = m-2; ~j; --j) {
            if(a[i][j] != a[i][j+1]) {
                r[i][j] = r[i][j+1];
            }
        }
    }
    //  Deal with each column 
    for(int i = 1; i < n; ++i) {
        for(int j = 0; j < m; ++j) {
            if(a[i][j] != a[i-1][j]) {
                h[i][j] = h[i-1][j] + 1;
                l[i][j] = max(l[i][j], l[i-1][j]);
                r[i][j] = min(r[i][j], r[i-1][j]);
            }
        }
    }
    int ans1 = 0;
    int ans2 = 0;
    for(int i = 0; i < n; ++i) {
        for(int j = 0; j < m; ++j) {
            int c = r[i][j] - l[i][j] + 1;
            int d = h[i][j];
            ans1 = max(ans1, min(c*c, d*d));
            ans2 = max(ans2, c*d);
        }
    }
    printf("%d\n%d\n", ans1, ans2);
    return 0;
}