Advertisement
Guest User

Untitled

a guest
Jun 23rd, 2017
50
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.45 KB | None | 0 0
  1. #define _CRT_SECURE_NO_DEPRECATE
  2. #define _USE_MATH_DEFINES
  3. #include <cstdio>
  4. #include <iostream>
  5. #include <vector>
  6. #include <queue>
  7. #include <deque>
  8. #include <stack>
  9. #include <algorithm>
  10. #include <cmath>
  11. #include <map>
  12. #include <set>
  13. #include <ctime>
  14. #include <sstream>
  15. #include <numeric>
  16.  
  17. #define sz(x) (int)(x).size()
  18. #define all(x) (x).begin(),(x).end()
  19. #define EPS 1e-9
  20. #define INF INT_MAX
  21. #define SQR(X) (X) * (X)
  22. #define round(x) (int)floor((x) + 0.5 + EPS)
  23.  
  24. using namespace std;
  25.  
  26. typedef pair <int, int> pii;
  27. typedef vector <int> vi;
  28. typedef vector <vi> vvi;
  29. typedef vector <pii> vpii;
  30. typedef vector <vpii> vvpii;
  31. typedef vector <string> vs;
  32. typedef unsigned int uint;
  33.  
  34. const int N = 100;
  35. int a[N][N] = {0};
  36. int n, m;
  37. int dx[] = {0, 0, 1, -1};
  38. int dy[]  = {1, -1, 0, 0};
  39.  
  40.  
  41. void DFS(int y, int x)
  42. {
  43.     a[y][x] = 1;
  44.     for (int i = 0; i < 4; i++)
  45.     {
  46.         int nx = x;
  47.         int ny = y;
  48.         nx += dx[i];
  49.         ny += dy[i];
  50.         if (nx < 0 || nx > m - 1) continue;
  51.         if (ny < 0 || ny > n - 1) continue;
  52.         if (a[ny][nx]) continue;
  53.         DFS(ny, nx);
  54.     }
  55. }
  56.  
  57. int main()
  58. {
  59. #ifndef ONLINE_JUDGE
  60.     freopen("d.in", "r", stdin);
  61.     freopen("d.out", "w", stdout);
  62. #endif
  63.     scanf("%d%d", &n, &m);
  64.     for (int i = 0; i < n; i++)
  65.         for (int j = 0; j < m; j++)
  66.             scanf("%d", &a[i][j]);
  67.     int res = 0;
  68.     for (int i = 0; i < n; i++)
  69.         for (int j = 0; j < m; j++)
  70.         {
  71.             if (a[i][j]) continue;
  72.             DFS(i, j);
  73.             res++;
  74.         }
  75.     printf("%d", res);
  76.     return 0;
  77. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement