b123 - 最大矩形 (Area)
題目描述
題目給定一個由 0 和 1 组成的矩陣，其中 0 代表空地，1 代表障碍物。要求找出矩陣中最大的矩形空地面積。
解題思路
本題使用動態規劃 (Dynamic Programming) 的方法來解決。首先，對於每一行，計算從該行每一列向左延伸的最大連續 0 的數量，並儲存在 dp 陣列中。然後，對於每一列，以該列為矩形的底部，向上延伸，計算以該列為底，高度為 h 的矩形面積，並更新最大面積。
具體來說，dp[i][j] 儲存的是矩陣 a[i][j] 左邊（包含自身）連續 0 的數量。然後，對於每一列 j，遍歷每一行 i，如果 a[i][j] 為 0，則計算以 (i, j) 為右下角的矩形的最大高度，並計算矩形面積，更新最大面積。
複雜度分析
- 時間複雜度: O(n^3)
- 空間複雜度: O(n^2)
程式碼
#include <iostream>
using namespace std;
int n,m,dp[201][201],ans;
bool a[201][201];
int main(){
while(cin >> n >> m){
for(int i=0;i<201;++i){
for(int j=0;j<201;++j){
dp[i][j]=0;
a[i][j]=0;
}
}
ans=0;
for(int i=0;i<n;++i)
for(int j=0;j<m;++j)
cin >> a[i][j];
for(int i=0;i<n;++i){
for(int j=0;j<m;++j){
if(a[i][j]){
for(int jj=j;jj>=0;--jj){
if(a[i][jj])
++dp[i][j];
else
break;
}
}
}
}
for(int i=0;i<n;++i){
for(int j=0;j<m;++j){
if(a[i][j]){
if(dp[i][j]*(n-i)>ans){
for(int k=1;k<=dp[i][j];++k){
int tmp=0;
for(int ii=i;ii<n;++ii){
if(dp[ii][j]>=k)
tmp+=k;
else{
ans=max(tmp,ans);
break;
}
}
}
}
}
}
}
cout << ans << "\n";
}
}