e560 - 10074 - Take the Land
題目描述
題目要求找出一個二維地圖中，由 0 表示的、面積最大的矩形區域。地圖由 1 和 0 組成，1 表示有樹木，0 表示空地。
解題思路
程式碼使用動態規劃 (Dynamic Programming) 的方法來解決這個問題。首先，對於地圖中的每一行，計算從該行中的每一列開始，連續有多少個 0。這個資訊儲存在 dp 陣列中。然後，對於地圖中的每一列，檢查以該列為右邊界的矩形的最大高度。最後，計算以每一列為右邊界的最大矩形面積，並更新最大面積。
具體來說，dp[i][j] 儲存的是地圖第 i 行，從第 j 列開始，連續有多少個 0。然後，對於每一列 j，程式碼遍歷每一行 i，如果 a[i][j] 為 0，則 dp[i][j] 的值等於 dp[i][j-1] + 1。如果 a[i][j] 為 1，則 dp[i][j] 為 0。
計算最大矩形面積時，程式碼遍歷每一列 j，對於每一列，計算以該列為右邊界的最大矩形面積。對於每一行 i，如果 a[i][j] 為 0，則計算以該行和該列為右下角的矩形面積。矩形的寬度由 dp[i][j] 決定，高度由從第 i 行向上連續有多少個 0 決定。
複雜度分析
- 時間複雜度: O(n^3)
- 空間複雜度: O(n^2)
程式碼
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define max( x, y ) ( ((x)>(y)) ? (x):(y) )
#include <stdio.h>
int n,m,dp[101][101],ans;
char a[101][101];
inline int read(){
int a(0);
char c('0');
while(c>='0'){
a=(a<<3)+(a<<1)+c-'0';
c=getchar_unlocked();
}
return a;
}
inline void write(int x) {
int stk[9],*ptr(&stk[0]);
while(x){*ptr=x%10;x/=10;++ptr;}
while(--ptr>=(&stk[0])){putchar_unlocked(*ptr+'0');}
}
int main(){
while(n=read()){
m=read();
if(n==0&&m==0)break;
for(int i=0;i<101;++i)
for(int j=0;j<101;++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){
a[i][j]=read();
a[i][j]=!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;
}
}
}
write(ans);
putchar_unlocked('\n');
}
}