AlexandruT

Fill

Jul 21st, 2015
60
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.17 KB | None | 0 0
  1. #include <iostream>
  2. #include <fstream>
  3. #include <stack>
  4.  
  5. using namespace std;
  6. stack <pair <int, int> > t;
  7.  
  8. int a[1000][1000];
  9.  
  10. int Fill(int i, int j)
  11. {
  12.     t.push(make_pair(i, j));
  13.     int cnt = 0;
  14.     while(!t.empty())
  15.     {
  16.         i = t.top().first;
  17.         j = t.top().second;
  18.         t.pop();
  19.         a[i][j] = 0;
  20.         cnt++;
  21.         if(a[i + 1][j] == 1)
  22.             t.push(make_pair(i + 1, j));
  23.         if(a[i - 1][j] == 1)
  24.             t.push(make_pair(i - 1, j));
  25.         if(a[i][j + 1] == 1)
  26.             t.push(make_pair(i, j + 1));
  27.         if(a[i][j - 1] == 1)
  28.             t.push(make_pair(i, j - 1));
  29.     }
  30.     return cnt;
  31. }
  32.  
  33. int main()
  34. {
  35.     int i, j, l, c, nrob, obmax, x;
  36.     ifstream fin("date.in");
  37.     fin >> l >> c;
  38.     for(i = 1; i <= l; i++)
  39.         for(j = 1; j <= c; j++)
  40.             fin >> a[i][j];
  41.     fin.close();
  42.     nrob = obmax = 0;
  43.     for(i = 1; i <= l; i++)
  44.     {
  45.         for(j = 1; j <= c; j++)
  46.         {
  47.             if(a[i][j] == 1)
  48.             {
  49.                 nrob++;
  50.                 x = Fill(i, j);
  51.                 obmax = max(obmax, x);
  52.             }
  53.         }
  54.     }
  55.     cout << nrob;
  56.     return 0;
  57. }
Advertisement
Add Comment
Please, Sign In to add comment