【姐妹題】ZeroJudge b123: 最大矩形 (Area)
【題目敘述】https://tioj.ck.tp.edu.tw/problems/1063
【解題想法】
- len[j]：紀錄col-j看到的，從前面的rows累積過來的「連續長度」(圖例中的 length 方向)。
- 循序檢查每一列(row)，更新len[j]。
- len[j] = a[i][j] ? len[j] + 1 : 0;
- 檢查每一列時，從每一個col-j 由後往前檢查，直到遇到 len[k] < len[j]。
- 0 <= k < j
- 新增面積值 len[j] * (j-k)。
- 更新目前為止的最大面積 mx。
#include <iostream>
#include <cstring>
using namespace std;
int a[205][205];
int len[205];
int main(){
int M, N;
while (cin >> M >> N){
memset(a, 0, sizeof(0));
memset(len, 0, sizeof(len));
for (int i=0; i<M; i++){
for (int j=0; j<N; j++){
cin >> a[i][j];
}
}
int mx = 0;
for (int i=0; i<M; i++){
for (int j=0; j<N; j++){
len[j] = a[i][j] ? len[j] + 1 : 0;
int mn = len[j];
int k = j - 1;
mx = max(mx, mn);
while (k >= 0 && a[i][k] == 1){
mn = min(mn, len[k]);
k--;
mx = max(mx, mn * (j-k));
}
}
}
cout << mx << '\n';
}
return 0;
}