解いた問題のソースコードと解説など。


POJ 3494 Largest Submatrix of All 1’s

問題

0と1からなるnxmのマスが与えられる。この中に含まれる1のみからなるx軸とy軸に平行な長方形で最大の長方形の面積を求めよ。

やりかた

ヒストグラム内の最大長方形の面積を求めるアルゴリズムを応用する。マスから一行読むごとにこのアルゴリズムを実施する。そのときにどれだけy軸方向に1が連続しているかを列ごとに蓄積しておくことで、その値をその行を読んだときのヒストグラムの高さとして考える事ができる。計算量O(nm)

以下ソース。

int m, n;
int h[2010];
int R[2010], L[2010];

int largest_hist(){
  stack<int> S;
  for(ll i = 0; i < n; i++){
    while(S.size() && h[S.top()] >= h[i]) S.pop();
    L[i] = S.size() ? S.top() + 1 : 0;
    S.push(i);
  }
  S = stack<int>();
  for(ll i = n - 1; i >= 0; i--){
    while(S.size() && h[S.top()] >= h[i]) S.pop();
    R[i] = S.size() ? S.top() : n;
    S.push(i);
  }

  int ans = 0;
  for(int i = 0; i < n; i++)
    ans = max(ans, h[i] * (R[i] - L[i]));
  return ans;
}

int main(int argc, char **argv){
  while(cin >> m >> n){
    FILL(h, 0);
    int ans = 0;
    for(int i = 0; i < n; i++){
      for(int j = 0; j < m; j++){
	int d; scanf("%d", &d);
	h[j] = d ? h[j] + 1 : 0;
      }
      ans = max(ans, largest_hist());
    }
    cout << ans << endl;
  }
  return 0;
}
罪を憎んで人は憎まずにセクシー