Pagini recente » Cod sursa (job #127657) | Cod sursa (job #3268596)
#include <bits/stdc++.h>
using namespace std;
const int N_MAX = 202, M_MAX = 202;
int N, M;
int m[N_MAX][M_MAX]; // m[i][j] = 2 => avem un 0 deja folosit
int col[N_MAX][M_MAX];
int used[N_MAX][M_MAX]; // = suma partiala pe matrice pt nr de celule de 2
char s[M_MAX];
void SetInput(string name)
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
(void)!freopen((name + ".in").c_str(), "r", stdin);
(void)!freopen((name + ".out").c_str(), "w", stdout);
}
void ReadInput()
{
cin >> N >> M;
cin.getline(s, M_MAX);
for(int i = 1, j; i <= N; i++)
{
cin.getline(s + 1, M_MAX);
for(j = 1; j <= M; j++)
m[i][j] = s[j] - '0';
}
}
void Border()
{
for(int i = 0; i <= N + 1; i++)
m[i][0] = m[i][M+1] = 1;
for(int j = 0; j <= M + 1; j++)
m[0][j] = m[N+1][j] = 1;
}
inline int CalcUsed(int r1, int c1, int r2, int c2)
{
if(used[r2][c2] == 0)
return 0;
return used[r2][c2] - used[r2][c1-1] - used[r1-1][c2] + used[r1-1][c2-1];
}
int FindMaxRecArea()
{
int maxArea = 0;
pair<int, int> recPos, recSize;
stack<pair<int, int> > peaks; /// {lin[i][j], j} unde i este ramane constant
peaks.push(make_pair(0, 0));
for(int i = 1, j; i <= N; i++)
{
peaks.top().second = 0;
for(j = 1; j <= M + 1; j++) /// j <= M + 1 pt ca m[i][M+1] = 1 pt orice i si se reseteaza stack-ul
{
used[i][j] = used[i-1][j] + used[i][j-1] - used[i-1][j-1] + (m[i][j] == 2);
col[i][j] = m[i][j] == 1 ? 0 : col[i-1][j] + 1;
pair<int, int> top;
int area;
while(not peaks.empty() && peaks.top().first > col[i][j])
{
top = peaks.top();
peaks.pop();
area = top.first * (j - 1 - peaks.top().second) - CalcUsed(i - top.first + 1, peaks.top().second + 1, i, j - 1);
if(area > maxArea)
{
maxArea = area;
recPos = make_pair(i, j-1);
recSize = make_pair(j - 1 - peaks.top().second, top.first);
}
}
if(col[i][j] == 0)
peaks.top().second = j;
else
peaks.push(make_pair(col[i][j], j));
}
}
for(int i = recPos.first - recSize.second + 1; i <= recPos.first; i++)
for(int j = recPos.second - recSize.first + 1; j <= recPos.second; j++)
m[i][j] = 2;
return maxArea;
}
void Solve()
{
int firstArea = FindMaxRecArea();
int secondArea = FindMaxRecArea();
cout << firstArea + secondArea;
}
int main()
{
SetInput("bmatrix");
ReadInput();
Border();
Solve();
return 0;
}