Pagini recente » Cod sursa (job #1318905) | Cod sursa (job #1363822) | Cod sursa (job #690011) | Cod sursa (job #3183481) | Cod sursa (job #1988671)
#include <iostream>
#include <fstream>
#include <stack>
using namespace std;
const int nMax = 205;
const int mMax = 205;
const int UP = 0;
const int LEFT = 1;
const int DOWN = 2;
const int RIGHT = 3;
int n, m;
char a[nMax][mMax];
char t[nMax][mMax];
int maxMatrix[4][nMax];
int rasp = 0;
void citire()
{
ifstream in("bmatrix.in");
in >> n >> m;
for(int i = 1; i <= n; ++i)
in >> (a[i] + 1);
in.close();
}
void GetMax(int ret[])
{
static int height[mMax];
static int firstSmallerSt[mMax];
static int firstSmallerDr[mMax];
stack<int> st;
for(int i = 1; i <= m; ++i)
height[i] = 0;
height[0] = height[m + 1] = -1;
int length;
for(int i = 1; i <= n; ++i) //fixam linia de jos
{
for(int j = 1; j <= m; ++j)
{
if(a[i][j] == '0')
height[j]++;
else
height[j] = 0;
}
st.push(1 - 1);
for(int j = 1; j <= m; ++j)
{
while(st.empty() == false && height[j] <= height[st.top()])
st.pop();
firstSmallerSt[j] = st.top();
st.push(j);
}
while(st.empty() == false)
st.pop();
st.push(m + 1);
for(int j = m; j >= 1; --j)
{
while(st.empty() == false && height[j] <= height[st.top()])
st.pop();
firstSmallerDr[j] = st.top();
st.push(j);
}
while(st.empty() == false)
st.pop();
for(int j = 1; j <= m; ++j)
{
if(height[j] == 0)
continue;
length = firstSmallerDr[j] - firstSmallerSt[j] - 1;
ret[i] = max(ret[i], length * height[j]);
}
}
}
void RotateMatrix()
{
swap(n, m);
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= m; ++j)
t[i][j] = a[j][n - i + 1];
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= m; ++j)
a[i][j] = t[i][j];
}
void rezolvare()
{
for(int i = 0; i < 4; ++i)
{
GetMax(maxMatrix[i]);
RotateMatrix();
}
for(int i = 1; i < n; ++i)
for(int j = i + 1; j <= n; ++j)
rasp = max(rasp, maxMatrix[UP][i] + maxMatrix[DOWN][n - j + 1]);
for(int i = 1; i < m; ++i)
for(int j = i + 1; j <= m; ++j)
rasp = max(rasp, maxMatrix[LEFT][i] + maxMatrix[RIGHT][m - j + 1]);
}
void afisare()
{
ofstream out("bmatrix.out");
out << rasp;
out.close();
}
int main()
{
citire();
rezolvare();
afisare();
return 0;
}