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; }