Pagini recente » Cod sursa (job #1688243) | Cod sursa (job #2615125) | Cod sursa (job #1717180) | Cod sursa (job #1013191) | Cod sursa (job #3268452)
#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 lin[N_MAX][M_MAX], 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];
pair<int, int> bestRec[N_MAX][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';
}
}
inline int CalcUsed(int r1, int c1, int r2, int c2)
{
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> pos = make_pair(0, 0);
for(int i = 1, j; i <= N; i++)
for(j = 1; j <= M; j++)
{
used[i][j] = used[i-1][j] + used[i][j-1] - used[i-1][j-1] + (m[i][j] == 2);
//cerr << i << ' ' << j << ' ' << used[i][j] << '\n';
if(m[i][j] == 1)
{
lin[i][j] = col[i][j] = 0;
bestRec[i][j] = make_pair(0, 0);
}
else /// if m[i][j] = 0 sau 2
{
lin[i][j] = lin[i][j-1] + 1;
col[i][j] = col[i-1][j] + 1;
int r = min(bestRec[i-1][j-1].first + 1, lin[i][j]);
int c = min(bestRec[i-1][j-1].second + 1, col[i][j]);
int area = r * c - CalcUsed(i-c+1, j-r+1, i, j);
int area1 = lin[i][j] - CalcUsed(i, j - lin[i][j] - 1, i, j);
if(area1 > area)
{
area = area1;
r = lin[i][j];
c = 1;
}
int area2 = col[i][j] - CalcUsed(i - col[i][j] - 1, j, i, j);
if(area2 > area)
{
area = area2;
r = 1;
c = col[i][j];
}
bestRec[i][j] = make_pair(r, c);
if(area > maxArea)
{
maxArea = area;
pos = make_pair(i, j);
}
}
}
pair<int, int> rec = bestRec[pos.first][pos.second];
for(int i = pos.first - rec.second + 1; i <= pos.first; i++)
for(int j = pos.second - rec.first + 1; j <= pos.second; j++)
m[i][j] = 2;
cerr << pos.first << ' ' << pos.second << " --- " << rec.first << ' ' << rec.second << ' ' << maxArea << '\n';
for(int i = 1; i <= N; i++, cerr << '\n')
for(int j = 1; j <= M; j++)
cerr << m[i][j] << ' ';
cerr << bestRec[1][7].first << ' ' << bestRec[1][7].second << '\n';
return maxArea;
}
void Solve()
{
int firstArea = FindMaxRecArea();
int secondArea = FindMaxRecArea();
cout << firstArea + secondArea;
}
int main()
{
SetInput("bmatrix");
ReadInput();
Solve();
return 0;
}