Advertisement
kburnik

C++ - Zadatak Poplava :: BFS obilazak matrice

Jan 6th, 2013
161
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.00 KB | None | 0 0
  1. /*
  2.     Zadatak: Poplava
  3.    
  4.     Izracunati povrsinu ogradjenog dijela matrice oko tocke zadane koordinatama
  5.     (drugim i trecim brojem kod unosa)
  6.    
  7.     KLASICNI BFS SA BROJANJEM POLJA
  8.    
  9.     Autor: Kristijan Burnik, Udruga informatičara Božo Težak
  10.  
  11.     GMail: kristijanburnik
  12.  
  13. */
  14. #include <iostream>
  15. #include <cstdlib>
  16. #include <algorithm>
  17. #include <vector>
  18. #include <queue>
  19.  
  20.  
  21. using namespace std;
  22.  
  23. typedef pair <int, int> pos;
  24. #define X first
  25. #define Y second
  26. #define mp make_pair
  27. int N,M;
  28.  
  29. bool canmove( pos a ) {
  30.     return (a.X >=0 && a.X < N) && (a.Y >=0 && a.Y < M) && (mat[a.X][a.Y] != '#');
  31. }
  32.  
  33. // uzorak kretanja
  34. pos DELTA[4] = {mp(-1,0),mp(1,0),mp(0,-1),mp(0,1)};
  35. vector < pos > delta(DELTA,DELTA+4);
  36. const int DS = delta.size();
  37.  
  38. // matrice za obilazak
  39. vector < vector <char> > mat;
  40. vector < vector <bool> > seen;
  41.  
  42.  
  43. int floodfill(pos current) {
  44.     queue <pos> q;
  45.     q.push(current);
  46.     seen[current.X][current.Y] = true;
  47.     int count = 0;
  48.     while (!q.empty()) {
  49.         current = q.front(); q.pop();
  50.         count++;
  51.         for (int i = 0 ; i < DS; i++) {
  52.             pos next = mp(current.X+delta[i].X,current.Y+delta[i].Y);
  53.             if (canmove(next) && !seen[next.X][next.Y]) {
  54.                 q.push(next);
  55.                 seen[next.X][next.Y] = true;
  56.             }
  57.         }
  58.     }
  59.  
  60.     return count;
  61. }
  62.  
  63. int main(void) {
  64.  
  65.     pos current;
  66.     cin >> N >> M >> current.X >> current.Y;
  67.     current.X--; current.Y--;
  68.  
  69.     mat.resize(N); seen.resize(N);
  70.     for (int i = 0; i < N; i++) {
  71.         mat[i].resize(M);
  72.         seen[i].resize(M);
  73.         for(int j = 0; j < M; j++) cin >> mat[i][j];
  74.    }
  75.    cout << floodfill(current) << endl;
  76.  
  77.    return 0;
  78. }
  79.  
  80. // Primjeri //
  81. /*
  82.  
  83. 8 8 1 1
  84. ........
  85. #.#.#.#.
  86. ########
  87. .#....#.
  88. .#..#.#.
  89. ....#...
  90. ########
  91. ........
  92.  
  93. 8 8 4 1
  94. ........
  95. #.#.#.#.
  96. ########
  97. .#....#.
  98. .#..#.#.
  99. ....#...
  100. ########
  101. ........
  102.  
  103. 8 8 8 3
  104. ........
  105. #.#.#.#.
  106. ########
  107. .#....#.
  108. .#..#.#.
  109. ....#...
  110. ########
  111. ........
  112.  
  113.  
  114. */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement