v 0. Pasted by slipstak2 as cpp at 2010-11-29 18:21:32 MSK and set expiration to never.

Paste will expire never.

  1. // Меньшиков. Тренировка 7.
  2. // 7F. Удаление клеток [remsquar]
  3. // ibelyaev: 29Nov2010
  4. #include <iostream>
  5. #include <cstdio>
  6. #include <queue>
  7.  
  8. using namespace std;
  9.  
  10. const int max_size = 100+5;
  11. int n,m;
  12. char mas[max_size][max_size];
  13. void input()
  14. {
  15.     cin>>n>>m;
  16.     for (int i=0;i<n;i++)
  17.     {
  18.         getchar(); // переход на новую строку
  19.         for (int j=0;j<m;j++)
  20.         {
  21.             mas[i][j] = getchar();
  22.         }       
  23.     }
  24. }
  25. struct point
  26. {
  27.     int x,y;
  28.     point(){}
  29.     point(int X, int Y)
  30.     {
  31.         x = X; y = Y;
  32.     }
  33. };
  34. int moveX[4] = {0,1,0,-1};
  35. int moveY[4] = {1,0,-1,0};
  36. bool correct(int x, int y)
  37. {
  38.     if (x<0 || y<0)
  39.         return false;
  40.     if (x>=n || y>=m)
  41.         return false;
  42.     return true;
  43. }
  44. void bfs(int x, int y)
  45. {
  46.     queue<point> q;
  47.     q.push(point(x,y));
  48.     while (!q.empty())
  49.     {
  50.         point cur = q.front(); q.pop();
  51.         for (int i=0;i<4;i++)
  52.         {
  53.             int x = cur.x + moveX[i];
  54.             int y = cur.y + moveY[i];
  55.             if (correct(x,y) && mas[x][y] == '#')
  56.             {
  57.                 q.push(point(x,y));
  58.                 mas[x][y] = '.';
  59.             }
  60.         }
  61.     }
  62. }
  63. void solve()
  64. {
  65.     int amount = 0;
  66.     for (int i=0;i<n;i++) {
  67.         for (int j=0;j<m;j++) {
  68.             if (mas[i][j] == '#')
  69.             {
  70.                 mas[i][j] = '.';
  71.                 bfs(i,j);
  72.                 amount++;
  73.             }
  74.         }
  75.     }
  76.     cout<<amount;
  77. }
  78. int main()
  79. {
  80.     freopen("input.txt","r",stdin);
  81.     freopen("output.txt","w",stdout);
  82.    
  83.     input();
  84.     solve();
  85.     return 0;
  86. }


Editing is locked.