題目連結: https://tioj.ck.tp.edu.tw/problems/1063
# 內容
在一個 M x N 的區域內，散落了許多不同的障礙物，我們想要知道的是，在這個 M x N 的區域內，最大的矩形空地面積是多少？倘若我們用 0 與 1 表示這個區域內的空地狀況：0 代表這個子區域已被障礙物覆蓋，1 代表這個子區域仍為空地，我們假設每一個 0 或 1 所代表的子區域面積為 1，那麼在下面這個例子中（M=4，N=5），最大的矩形空地為陰影所覆蓋的區域，其面積為 8。
在本題中，請依據輸入輸出的規定，針對輸入的地圖，輸出其最大的矩形空地面積。
# 思路
先算出從左到右有多少連續，再對每個數字往上尋找高，記得，再找高的途中如果有遇到比自己小的數字，數字要更新喔！！
畫了圖你就知道
# 程式碼
#include <bits/stdc++.h> | |
using namespace std; | |
int mp[201][201]={}; | |
int m, n; | |
int main() { | |
while(cin>>m>>n){ | |
for(int i=0;i<m;i++) | |
for(int j=0;j<n;j++) | |
cin>>mp[i][j]; | |
for(int i =0;i<m;i++) | |
for(int j =1;j<n;j++) | |
if(mp[i][j]) | |
mp[i][j]=mp[i][j-1]+1; | |
int ans = 0; | |
for(int i = 0;i<m;i++){ | |
for(int j =0;j<n;j++){ | |
int width = 1<<20; | |
for(int h = 0;i-h>=0&&mp[i-h][j];h++){ | |
width = min(width,mp[i-h][j]); | |
int area = width*(h+1); | |
ans = max(ans,area); | |
} | |
} | |
} | |
cout<<ans<<endl; | |
} | |
return 0; | |
} |
