Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*
- Zadatak: Poplava
- Izracunati povrsinu ogradjenog dijela matrice oko tocke zadane koordinatama
- (drugim i trecim brojem kod unosa)
- KLASICNI BFS SA BROJANJEM POLJA
- Autor: Kristijan Burnik, Udruga informatičara Božo Težak
- GMail: kristijanburnik
- */
- #include <iostream>
- #include <cstdlib>
- #include <algorithm>
- #include <vector>
- #include <queue>
- using namespace std;
- typedef pair <int, int> pos;
- #define X first
- #define Y second
- #define mp make_pair
- int N,M;
- bool canmove( pos a ) {
- return (a.X >=0 && a.X < N) && (a.Y >=0 && a.Y < M) && (mat[a.X][a.Y] != '#');
- }
- // uzorak kretanja
- pos DELTA[4] = {mp(-1,0),mp(1,0),mp(0,-1),mp(0,1)};
- vector < pos > delta(DELTA,DELTA+4);
- const int DS = delta.size();
- // matrice za obilazak
- vector < vector <char> > mat;
- vector < vector <bool> > seen;
- int floodfill(pos current) {
- queue <pos> q;
- q.push(current);
- seen[current.X][current.Y] = true;
- int count = 0;
- while (!q.empty()) {
- current = q.front(); q.pop();
- count++;
- for (int i = 0 ; i < DS; i++) {
- pos next = mp(current.X+delta[i].X,current.Y+delta[i].Y);
- if (canmove(next) && !seen[next.X][next.Y]) {
- q.push(next);
- seen[next.X][next.Y] = true;
- }
- }
- }
- return count;
- }
- int main(void) {
- pos current;
- cin >> N >> M >> current.X >> current.Y;
- current.X--; current.Y--;
- mat.resize(N); seen.resize(N);
- for (int i = 0; i < N; i++) {
- mat[i].resize(M);
- seen[i].resize(M);
- for(int j = 0; j < M; j++) cin >> mat[i][j];
- }
- cout << floodfill(current) << endl;
- return 0;
- }
- // Primjeri //
- /*
- 8 8 1 1
- ........
- #.#.#.#.
- ########
- .#....#.
- .#..#.#.
- ....#...
- ########
- ........
- 8 8 4 1
- ........
- #.#.#.#.
- ########
- .#....#.
- .#..#.#.
- ....#...
- ########
- ........
- 8 8 8 3
- ........
- #.#.#.#.
- ########
- .#....#.
- .#..#.#.
- ....#...
- ########
- ........
- */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement