Advertisement
Guest User

Untitled

a guest
Mar 23rd, 2017
62
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.21 KB | None | 0 0
  1. #include <iostream>
  2. #include <fstream>
  3. #include <vector>
  4. #include <queue>
  5. #include <unordered_set>
  6.  
  7. using namespace std;
  8.  
  9. const int nMax = 305;
  10. const int mMax = 305;
  11. const int dx[] = {-1, 1, 0, 0};
  12. const int dy[] = {0, 0, -1, 1};
  13.  
  14. ofstream out("zone2.out");
  15.  
  16. struct zona
  17. {
  18.     int marime;
  19.     unordered_set<int> vecini;
  20. };
  21.  
  22. int n, m, k;
  23. char a[nMax][mMax];
  24. int zonaId[nMax][mMax];
  25. zona zone[nMax*mMax];
  26. bool deleted[nMax*mMax];
  27. bool viz[nMax][mMax];
  28. int nrZone;
  29. int rasp;
  30.  
  31. void citire()
  32. {
  33.     ifstream in("zone2.in");
  34.     in >> n >> m >> k;
  35.     for(int i = 1; i <= n; ++i)
  36.         in >> (a[i]+1);
  37.     in.close();
  38. }
  39.  
  40. int CreateZone(int startX, int startY)
  41. {
  42.     int ret = 1;
  43.     queue<pair<int, int> > q;
  44.     q.push(make_pair(startX, startY));
  45.     zonaId[startX][startY] = nrZone;
  46.  
  47.     int newx, newy;
  48.     pair<int, int> p;
  49.     while(q.empty() == false)
  50.     {
  51.         p = q.front();
  52.         q.pop();
  53.  
  54.         for(int d = 0; d < 4; ++d)
  55.         {
  56.             newx = p.first + dx[d];
  57.             newy = p.second + dy[d];
  58.  
  59.             if(a[newx][newy] == a[startX][startY] && zonaId[newx][newy] == 0)
  60.             {
  61.                 zonaId[newx][newy] = nrZone;
  62.                 q.push(make_pair(newx, newy));
  63.                 ret++;
  64.             }
  65.         }
  66.     }
  67.     return ret;
  68. }
  69.  
  70. void SetVecini(int startX, int startY)
  71. {
  72.     queue<pair<int, int> > q;
  73.     q.push(make_pair(startX, startY));
  74.     viz[startX][startY] = true;
  75.  
  76.     int newx, newy;
  77.     pair<int, int> p;
  78.     while(q.empty() == false)
  79.     {
  80.         p = q.front();
  81.         q.pop();
  82.         for(int d = 0; d < 4; ++d)
  83.         {
  84.             newx = p.first + dx[d];
  85.             newy = p.second + dy[d];
  86.             if(newx < 1 || newx > n || newy < 1 || newy > m)
  87.                 continue;
  88.             if(zonaId[newx][newy] == zonaId[startX][startY])
  89.             {
  90.                 if(viz[newx][newy] == false)
  91.                 {
  92.                     q.push(make_pair(newx, newy));
  93.                     viz[newx][newy] = true;
  94.                 }
  95.             }
  96.             else
  97.                 zone[zonaId[startX][startY]].vecini.insert(zonaId[newx][newy]);
  98.  
  99.         }
  100.     }
  101. }
  102.  
  103. void DeleteZone(int ind)
  104. {
  105.     if(deleted[ind] == true)
  106.         return;
  107.     rasp -= zone[ind].marime;
  108.     deleted[ind] = true;
  109.     for(auto v:zone[ind].vecini)
  110.     {
  111.         zone[v].vecini.erase(ind);
  112.         if(zone[v].vecini.size() < k)
  113.             DeleteZone(v);
  114.     }
  115.     zone[ind].vecini.clear();
  116. }
  117.  
  118. void rezolvare()
  119. {
  120.     rasp = n * m;
  121.     for(int i = 1; i <= n; ++i)
  122.         for(int j = 1; j <= m; ++j)
  123.             if(zonaId[i][j] == 0)
  124.                 zone[++nrZone].marime = CreateZone(i, j);
  125.  
  126.     for(int i = 1; i <= n; ++i)
  127.         for(int j = 1; j <= m; ++j)
  128.             if(zone[zonaId[i][j]].vecini.size() == 0)
  129.                 SetVecini(i, j);
  130.     bool ok = true;
  131.     while(ok)
  132.     {
  133.         ok = false;
  134.         for(int i = 1; i <= nrZone; ++i)
  135.         {
  136.             if(deleted[i] == false && zone[i].vecini.size() < k)
  137.             {
  138.                 ok = true;
  139.                 DeleteZone(i);
  140.             }
  141.         }
  142.     }
  143.     out << rasp;
  144. }
  145.  
  146. int main()
  147. {
  148.     citire();
  149.     rezolvare();
  150.     return 0;
  151. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement