C++ - Zadatak Poplava :: BFS obilazak matrice

Jan 6th, 2013
103
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. /*
3.
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. */
RAW Paste Data