Advertisement
kalabukdima

BFS

Mar 20th, 2021
771
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.65 KB | None | 0 0
  1. #include <iostream>
  2. #include <queue>
  3. #include <array>
  4. #include <vector>
  5.  
  6. /*
  7. 5 8
  8. ....##..
  9. ..##.##.
  10. ###...##
  11. #.#..###
  12. #..####.
  13. */
  14.  
  15. struct Coord {
  16.     int i;
  17.     int j;
  18. };
  19.  
  20. int CountReachableFrom(std::vector<std::vector<bool>>& field, const Coord& start) {
  21.     const int n = field.size();
  22.     const int m = field.at(0).size();
  23.  
  24.     std::queue<Coord> queue;
  25.     queue.push(start);
  26.     field[start.i][start.j] = true;
  27.  
  28.     int count = 1;
  29.     while (!queue.empty()) {
  30.         const Coord current = queue.front();
  31.         queue.pop();
  32.  
  33.         for (const Coord delta : std::vector<Coord>{{0, 1}, {1, 0}, {0, -1}, {-1, 0}}) {
  34.             const Coord next{current.i + delta.i, current.j + delta.j};
  35.             if (next.i < 0 || next.j < 0 || next.i >= n || next.j >= m) {
  36.                 continue;
  37.             }
  38.             if (field[next.i][next.j] == false) {
  39.                 field[next.i][next.j] = true;
  40.                 queue.push(next);
  41.                 ++count;
  42.             }
  43.         }
  44.     }
  45.  
  46.     return count;
  47. }
  48.  
  49. int main(int, const char**) {
  50.     int n, m;
  51.     std::cin >> n >> m;
  52.     std::string unused;
  53.     std::getline(std::cin, unused);
  54.  
  55.     std::vector<std::vector<bool>> field(n, std::vector<bool>(m));
  56.     for (int i = 0; i < n; ++i) {
  57.         for (int j = 0; j < m; ++j) {
  58.             char ch;
  59.             std::cin >> ch;
  60.             if (ch == '#') {
  61.                 field[i][j] = true;
  62.             } else {
  63.                 field[i][j] = false;
  64.             }
  65.         }
  66.         std::getline(std::cin, unused);
  67.     }
  68.  
  69.     int answer = CountReachableFrom(field, {1, 4});
  70.     std::cout << answer << "\n";
  71.     return 0;
  72. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement