题解 | # City Game #
记为经典题目，给定大小为
的
矩形块，求其中最大的全是
的矩形块，时间复杂度为)
总代码：
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
#define debug(x) cout << #x << "= " << x << endl;
#define IOS ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define HelloWorld IOS;
void solve(){
int n, m; cin >> n >> m;
vector<vector<char> > a(n + 10, vector<char> (m + 10));
for(int i = 1; i <= n; i ++){
for(int j = 1; j <= m; j ++) cin >> a[i][j];
}
int ans = 0;
vector<vector<int> > h(n + 10, vector<int> (m + 10));
for(int i = 1; i <= n; i ++){
int sum = 0;
for(int j = 1; j <= m; j ++){
if(a[i][j] == 'F') sum ++;
else sum = 0;
h[i][j] = sum;
}
}
for(int j = 1; j <= m; j ++){
vector<int> b(n + 10);
for(int i = 1; i <= n; i ++) b[i] = h[i][j];
vector<int> l(n + 10), r(n + 10);
stack<int> sta;
for(int i = 1; i <= n; i ++){
while(sta.size() && b[sta.top()] >= b[i]) sta.pop();
if(sta.size()) l[i] = sta.top();
else l[i] = 0;
sta.push(i);
}
while(sta.size()) sta.pop();
for(int i = n; i >= 1; i --){
while(sta.size() && b[sta.top()] >= b[i]) sta.pop();
if(sta.size()) r[i] = sta.top();
else r[i] = n + 1;
sta.push(i);
}
for(int i = 1; i <= n; i ++){
ans = max(ans, (r[i] - l[i] - 1) * b[i]);
}
}
for(int j = 1; j <= m; j ++){
int sum = 0;
for(int i = 1; i <= n; i ++){
if(a[i][j] == 'F') sum ++;
sum = 0;
h[i][j] = sum;
}
}
for(int i = 1; i <= n; i ++){
vector<int> b(m + 10);
for(int j = 1; j <= m; j ++) b[j] = h[i][j];
vector<int> l(m + 10), r(m + 10);
stack<int> sta;
for(int j = 1; j <= m; j ++){
while(sta.size() && b[sta.top()] >= b[j]) sta.pop();
if(sta.size()) l[j] = sta.top();
else l[j] = 0;
sta.push(j);
}
while(sta.size()) sta.pop();
for(int j = m; j >= 1; j --){
while(sta.size() && b[sta.top()] >= b[j]) sta.pop();
if(sta.size()) r[j] = sta.top();
else r[j] = 0;
sta.push(j);
}
for(int j = 1; j <= m; j ++){
ans = max(ans, (r[j] - l[j] - 1) * b[j]);
}
}
cout << ans * 3 << endl;
return ;
}
signed main(){
HelloWorld;
int tt = 1;
cin >> tt;
while(tt --) solve();
return 0;
}
查看14道真题和解析
