Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <algorithm>
- #include <fstream>
- #include <vector>
- #define pii pair <int, int>
- using namespace std;
- bool liber[1010][1010];
- bool cp[1010][1010];
- int n, m, ltip, h;
- vector <pair <pii, pii>> best;
- int abest;
- vector <pair <pii, pii>> act;
- void verif(int x, int y)
- {
- if (!liber[x][y])
- return;
- int t1(0), t2(0);
- int l(0); /// cu cat ma duc in jos
- if (cp[x][y])
- t1++;
- else
- t2++;
- while (l + 1 < h && x + l + 1 <= n) {
- if (!liber[x + l + 1][y])
- break;
- if (cp[x + l + 1][y])
- t1++;
- else
- t2++;
- l++;
- }
- vector <pii> v;
- if (t1 >= ltip && t2 >= ltip)
- v.push_back({ x + l, y });
- for (int i(1); i < h && y + i <= m; i++) {
- int lmin(0);
- for (int j(0); j <= l; j++) {
- if (!liber[x + j][y + i])
- break;
- lmin++;
- }
- while ((l + 1) * (i + 1) > h || l >= lmin) {
- for (int j(y); j < y + i; j++) {
- if (cp[x + l][j])
- t1--;
- else
- t2--;
- }
- l--;
- }
- if (l == -1)
- break;
- for (int j(0); j <= l; j++) {
- if (cp[x + j][y + i])
- t1++;
- else
- t2++;
- }
- if (t1 >= ltip && t2 >= ltip)
- v.push_back({ x + l, y + i });
- }
- vector <pii> maxim;
- int amax(0);
- for (auto i : v) {
- if ((i.first - x + 1) * (i.second - y + 1) == amax)
- maxim.push_back(i);
- if ((i.first - x + 1) * (i.second - y + 1) > amax) {
- maxim.clear();
- maxim.push_back(i);
- amax = (i.first - x + 1) * (i.second - y + 1);
- }
- }
- if (maxim.empty())
- return;
- int q = x * x + y * x * y + 45;
- q %= maxim.size();
- pii ans = maxim[q];
- act.push_back({ { x, ans.first }, { y, ans.second } });
- for (int i(x); i <= ans.first; i++)
- for (int j(y); j <= ans.second; j++)
- liber[i][j] = 0;
- }
- int main()
- {
- ifstream in("input.in");
- in >> n >> m >> ltip >> h;
- vector <pii> v;
- for (int i(1); i <= n; i++) {
- for (int j(1); j <= m; j++) {
- v.push_back({ i, j });
- char c;
- in >> c;
- cp[i][j] = (c == 'T' ? 1 : 0);
- }
- }
- int x(1000);
- while (x--) {
- random_shuffle(v.begin(), v.end());
- act.clear();
- for (int i(1); i <= n; i++)
- for (int j(1); j <= m; j++)
- liber[i][j] = 1;
- //verif(1, 3);
- //verif(1, 3);
- for (pii i : v)
- verif(i.first, i.second);
- int aact(0);
- for (auto i : act) {
- aact += (i.second.first - i.first.first + 1) *
- (i.second.second - i.first.second + 1);
- }
- int s(act.size());
- if (aact > abest) {
- abest = aact;
- best.clear();
- best = act;
- }
- }
- ofstream out("afisare.out");
- out << best.size() << '\n';
- for (auto i : best) {
- out << i.first.first - 1 << ' ' << i.second.first - 1 << ' ';
- out << i.first.second - 1 << ' ' << i.second.second - 1 << '\n';
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement