Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <fstream>
- #include <vector>
- #include <queue>
- #include <unordered_set>
- using namespace std;
- const int nMax = 305;
- const int mMax = 305;
- const int dx[] = {-1, 1, 0, 0};
- const int dy[] = {0, 0, -1, 1};
- ofstream out("zone2.out");
- struct zona
- {
- int marime;
- unordered_set<int> vecini;
- };
- int n, m, k;
- char a[nMax][mMax];
- int zonaId[nMax][mMax];
- zona zone[nMax*mMax];
- bool deleted[nMax*mMax];
- bool viz[nMax][mMax];
- int nrZone;
- int rasp;
- void citire()
- {
- ifstream in("zone2.in");
- in >> n >> m >> k;
- for(int i = 1; i <= n; ++i)
- in >> (a[i]+1);
- in.close();
- }
- int CreateZone(int startX, int startY)
- {
- int ret = 1;
- queue<pair<int, int> > q;
- q.push(make_pair(startX, startY));
- zonaId[startX][startY] = nrZone;
- int newx, newy;
- pair<int, int> p;
- while(q.empty() == false)
- {
- p = q.front();
- q.pop();
- for(int d = 0; d < 4; ++d)
- {
- newx = p.first + dx[d];
- newy = p.second + dy[d];
- if(a[newx][newy] == a[startX][startY] && zonaId[newx][newy] == 0)
- {
- zonaId[newx][newy] = nrZone;
- q.push(make_pair(newx, newy));
- ret++;
- }
- }
- }
- return ret;
- }
- void SetVecini(int startX, int startY)
- {
- queue<pair<int, int> > q;
- q.push(make_pair(startX, startY));
- viz[startX][startY] = true;
- int newx, newy;
- pair<int, int> p;
- while(q.empty() == false)
- {
- p = q.front();
- q.pop();
- for(int d = 0; d < 4; ++d)
- {
- newx = p.first + dx[d];
- newy = p.second + dy[d];
- if(newx < 1 || newx > n || newy < 1 || newy > m)
- continue;
- if(zonaId[newx][newy] == zonaId[startX][startY])
- {
- if(viz[newx][newy] == false)
- {
- q.push(make_pair(newx, newy));
- viz[newx][newy] = true;
- }
- }
- else
- zone[zonaId[startX][startY]].vecini.insert(zonaId[newx][newy]);
- }
- }
- }
- void DeleteZone(int ind)
- {
- if(deleted[ind] == true)
- return;
- rasp -= zone[ind].marime;
- deleted[ind] = true;
- for(auto v:zone[ind].vecini)
- {
- zone[v].vecini.erase(ind);
- if(zone[v].vecini.size() < k)
- DeleteZone(v);
- }
- zone[ind].vecini.clear();
- }
- void rezolvare()
- {
- rasp = n * m;
- for(int i = 1; i <= n; ++i)
- for(int j = 1; j <= m; ++j)
- if(zonaId[i][j] == 0)
- zone[++nrZone].marime = CreateZone(i, j);
- for(int i = 1; i <= n; ++i)
- for(int j = 1; j <= m; ++j)
- if(zone[zonaId[i][j]].vecini.size() == 0)
- SetVecini(i, j);
- bool ok = true;
- while(ok)
- {
- ok = false;
- for(int i = 1; i <= nrZone; ++i)
- {
- if(deleted[i] == false && zone[i].vecini.size() < k)
- {
- ok = true;
- DeleteZone(i);
- }
- }
- }
- out << rasp;
- }
- int main()
- {
- citire();
- rezolvare();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement