hihocoder #1673 : 01間隔矩陣

hihocoder #1673 : 01間隔矩陣

題目

題目見 01間隔矩陣

大概意思就是 給一個只含有01的矩陣,找出最大的01間隔矩陣。
碼不是自己的,來自luoshaochuan

輸入:
5 7
0101010
1000101
0101010
1010101
0101010

輸出:
21

思路

解法是DP,按行掃,對於每個元素找出左邊界右邊界和高度。
找邊界的時候向左向右兩個loop來propagete, propagete的時候要注意高度的條件,即延伸方向元素的高度不能低於當前元素。

DP表格

假設矩陣存在A[N] [N]裡,左邊界L[N],右邊界R[N], 高度H[N].
DP的題真是,不畫表格真的不能理解,智商壓制。

程式碼

#include <iostream>
#include <string>
using namespace std;

#define maxn 2006

int R[maxn], L[maxn], H[maxn];
char A[maxn][maxn];

int main() {
    int n,m;
    cin >> n >> m;

    for(int i = 0; i < n;   i){
        cin >> A[i];
    }

    int ans = 0;

    for(int i = 0; i < n;   i){
        for(int j = 0; j < m;   j){
            if(i > 0 && A[i][j] != A[i-1][j])   H[j];
            else H[j] = 1;
        }

        for(int j = 0; j < m;   j) {
            L[j] = j;
            while(L[j] && H[j] <= H[L[j]-1] && A[i][L[j]] != A[i][L[j]-1])
                L[j] = L[L[j]-1];
        }

        for(int j = m-1; j >=0; --j){
            R[j] = j;
            while(R[j] < m-1 && H[j] <= H[R[j] 1] && A[i][R[j]] != A[i][R[j] 1])
                R[j] = R[R[j] 1];
        }

        for(int j = 0; j < m ;   j){
            ans = max(ans,H[j]*(R[j]-L[j] 1));
        }
    }

    cout << ans << endl;

    return 0;
}

最後吐槽SF的編輯器真是爛啊 。。。