[Offer收割]编程练习赛40 register

Ended

Participants:189

Verdict:Accepted
Score:100 / 100
Submitted:2017-12-17 13:45:21

Lang:G++

Edit
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <bits/stdc++.h>
using namespace std;
#define MAXN 1000
char mat[MAXN][MAXN+1];
int height[MAXN];
struct QItem { int p, h; } q[MAXN];
int main() {
    int n, m; scanf("%d%d", &n, &m);
    for (int i=0; i<n; ++i) { scanf("%s", mat[i]); }
    int mx = 0;
    memset(height, 0, sizeof(height));
    for (int i=0; i<n; ++i) {
        int h = 0, r = 0;
        for (int j=0; j<m; ++j) {
            height[j] = (i == 0 || mat[i][j] != mat[i-1][j]) ? height[j]+1 : 1;
            if (j == 0 || mat[i][j] == mat[i][j-1]) {
                h = r = 0;
                q[r++] = { j, height[j] };
                mx = max(1, mx);
            } else {
                int tj = j;
                while (h < r && q[r-1].h > height[j]) {
                    tj = q[r-1].p;
                    --r;
                }   
                q[r++] = { tj, height[j] };
                while (h < r && q[h].h+q[h].p <= j) { ++h; }
                mx = max(mx, min(q[h].h, j-q[h].p+1));
            }   
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX