CS Academy Surrounded Rectangle

リンク : https://csacademy.com/contest/archive/task/surrounded-rectangle/statement/

問題概要

N*Mの行列が与えられる。これは0,1から成る。0で完全に囲まれた1のみからなる長方形の面積を求めよ。完全に囲まれるとは、入力例を参照してほしい。

解説

やるだけ。
N,M<=1000より嫌な予感がしたが、実装するだけだった。1しかない長方形を探し、その外側がしっかり0で囲まれていることを確認してから、答えを更新する。

LL h, w, ans = -1, a[1100][1100];
LL dfs(int x, int y) {
    LL z = x, v = y;
    while (a[z + 1][y]) {
        z++;
        if (a[z][y - 1] != 0)return -1;
        if (z == h-1)return -1;
    }
    while (a[x][v + 1]) {
        v++;
        if (a[x - 1][v] != 0)return -1;
        if (v == w-1)return -1;
    }
    for (int i = x; i <= z; i++)
        for (int j = y; j <= v; j++) {
            if (a[i][j] != 1)return -1;
        }
    for (int i = x; i <= z; i++)
        if (a[i][v + 1] != 0)return -1;
    for (int i = y; i <= v; i++)
        if (a[z+1][i] != 0)return -1;
    if (a[z + 1][v + 1] !=0)return -1;
    if (a[z+1][y - 1] != 0)return -1;
    if (a[x - 1][v+1] != 0)return -1;
    return (z - x + 1)*(v - y + 1);
}
int main() {
    cin >> h >> w;
    rep(i, h)
        rep(j, w)
        cin >> a[i][j];
    rep(i, h)
        rep(j, w)
        if (i != 0 && j != 0 && i != h - 1 && j != w - 1)
            if (a[i - 1][j - 1] == 0 && a[i - 1][j] == 0 && a[i][j - 1] == 0)
                ans = max(ans, dfs(i, j));
    cout << ans << endl;
    return 0;
}