leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

bfs_floodfill.cpp (648B)

      1 // Matrix BFS/Flood fill
      2 
      3 typedef vector<vector<int>> Matrix;
      4 typedef queue<pair<int, int>> Queue;
      5 const vector<pair<int, int>> offsets = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
      6 
      7 int n, m;
      8 int valid(int x, int y) { return x >= 0 && x < n && y >= 0 && y < m; }
      9 
     10 void dfs(Matrix &mat, int x, int y) {
     11     Queue q;
     12 
     13     q.push({x, y}), mat[x][y] = 2;
     14     while (!q.empty()) {
     15         auto [a, b] = q.front();
     16         q.pop();
     17         for (auto [oa, ob] : offsets) {
     18             int x = a + oa, y = b + ob;
     19             if (!valid(x, y) || mat[x][y] == 0 || mat[x][y] != 1) continue;
     20             mat[x][y] = 2;
     21             q.push({x, y});
     22         }
     23     }
     24 }