leetcode

commit 521604886899958097481856e698ff88848abcbf
parent f4227ac904a43e34867d485f76976c700dfb1488
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Fri, 10 Feb 2023 14:44:53 +0100

Algorithm II: Day 8

Diffstat:
A
Problems/0130.cpp
 | 
53
+++++++++++++++++++++++++++++++++++++++++++++++++++++
A
Problems/1091.cpp
 | 
36
++++++++++++++++++++++++++++++++++++
M
README.md
 | 
7
+++++--
A
Templates/bfs_floodfill.cpp
 | 
29
+++++++++++++++++++++++++++++

4 files changed, 123 insertions(+), 2 deletions(-)
diff --git a/Problems/0130.cpp b/Problems/0130.cpp
@@ -0,0 +1,53 @@
+class Solution {
+  typedef vector<vector<char>> Matrix;
+  typedef queue<pair<int, int>> Queue;
+  const vector<pair<int, int>> offsets = {
+      { 0,  1},
+      { 0, -1},
+      { 1,  0},
+      {-1,  0}
+  };
+
+  int n, m;
+
+  int valid(int x, int y) { return x >= 0 && x < n && y >= 0 && y < m; }
+
+  void dfs(Matrix &board, int x, int y) {
+    Queue q;
+
+    q.push({x, y}), board[x][y] = '#';
+    while (!q.empty()) {
+      auto [a, b] = q.front();
+      q.pop();
+      for (auto [oa, ob] : offsets) {
+        int x = a + oa, y = b + ob;
+        if (!valid(x, y) || board[x][y] == 'X' || board[x][y] != 'O') continue;
+        board[x][y] = '#';
+        q.push({x, y});
+      }
+    }
+  }
+
+public:
+  void solve(Matrix &board) {
+    n = board.size(), m = board[0].size();
+
+    unordered_set<int> convert;
+    Queue q;
+    int group = 0;
+
+    for (int i = 0; i < n; i++) {
+      if (board[i][0] == 'O') dfs(board, i, 0);
+      if (board[i][m - 1] == 'O') dfs(board, i, m - 1);
+    }
+
+    for (int j = 0; j < m; j++) {
+      if (board[0][j] == 'O') dfs(board, 0, j);
+      if (board[n - 1][j] == 'O') dfs(board, n - 1, j);
+    }
+
+    for (int i = 0; i < n; i++)
+      for (int j = 0; j < m; j++)
+        if (board[i][j] != 'X') board[i][j] = board[i][j] == 'O' ? 'X' : 'O';
+  }
+};
diff --git a/Problems/1091.cpp b/Problems/1091.cpp
@@ -0,0 +1,36 @@
+class Solution {
+  int n;
+
+  bool valid(int x, int y) { return x >= 0 && x < n && y >= 0 && y < n; }
+
+public:
+  int shortestPathBinaryMatrix(vector<vector<int>> &grid) {
+    if (grid[0][0] == 1 || grid.back().back() == 1) return -1;
+    n = grid.size();
+
+    queue<pair<int, int>> q;
+    q.push({0, 0});
+    vector<pair<int, int>> offsets = {
+        {-1,  0},
+        {-1,  1},
+        { 0,  1},
+        { 1,  1},
+        { 1,  0},
+        { 1, -1},
+        { 0, -1},
+        {-1, -1}
+    };
+    while (!q.empty()) {
+      auto [a, b] = q.front();
+      q.pop();
+      if (a == n - 1 && b == n - 1) return grid[a][b] + 1;
+      for (auto [ox, oy] : offsets) {
+        int x = a + ox, y = b + oy;
+        if (!valid(x, y) || grid[x][y] > 0) continue;
+        grid[x][y] = grid[a][b] + 1;
+        q.push({x, y});
+      }
+    }
+    return -1;
+  }
+};
diff --git a/README.md b/README.md
@@ -15,9 +15,10 @@ if you have any questions.
 I have accumulated a list of most commonly used algorithms to serve as a base
 for solving problems.
 
-* [Union Find](Templates/Union_Find.cpp)
-* [MST from edge vector](Templates/MST_vector.cpp)
 * [MST from edge priority queue](Templates/MST_pq.cpp)
+* [MST from edge vector](Templates/MST_vector.cpp)
+* [Matrix BFS/Flood fill](Templates/bfs_floodfill.cpp)
+* [Union Find](Templates/Union_Find.cpp)
 
 ## Problems
 
@@ -103,6 +104,7 @@ for solving problems.
 |  0125  |    Easy    | [Valid Palindrome](Problems/0125.cpp)                                                            |
 |  0128  |   Medium   | [Longest Consecutive Sequence](Problems/0128.cpp)                                                |
 |  0129  |   Medium   | [Sum Root to Leaf Numbers](Problems/0129.cpp)                                                    |
+|  0130  |   Medium   | [Surrounded Regions](Problems/0130.cpp)                                                          |
 |  0131  |   Medium   | [Palindrome Partitioning](Problems/0131.cpp)                                                     |
 |  0133  |   Medium   | [Clone Graph](Problems/0133.cpp)                                                                 |
 |  0134  |   Medium   | [Gas Station](Problems/0134.cpp)                                                                 |
@@ -323,6 +325,7 @@ for solving problems.
 |  1061  |   Medium   | [Lexicographically Smallest Equivalent String](Problems/1061.cpp)                                |
 |  1071  |    Easy    | [Greatest Common Divisor of Strings](Problems/1071.cpp)                                          |
 |  1089  |    Easy    | [Duplicate Zeros](Problems/1089.cpp)                                                             |
+|  1091  |   Medium   | [Shortest Path in Binary Matrix](Problems/1091.cpp)                                              |
 |  1095  |    Easy    | [Find Numbers with Even Number of Digits](Problems/1095.cpp)                                     |
 |  1099  |    Easy    | [Replace Elements with Greatest Element on Right Side](Problems/1099.cpp)                        |
 |  1129  |   Medium   | [Shortest Path with Alternating Colors](Problems/1129.cpp)                                       |
diff --git a/Templates/bfs_floodfill.cpp b/Templates/bfs_floodfill.cpp
@@ -0,0 +1,29 @@
+// Matrix BFS/Flood fill
+
+typedef vector<vector<int>> Matrix;
+typedef queue<pair<int, int>> Queue;
+const vector<pair<int, int>> offsets = {
+    { 0,  1},
+    { 0, -1},
+    { 1,  0},
+    {-1,  0}
+};
+
+int n, m;
+int valid(int x, int y) { return x >= 0 && x < n && y >= 0 && y < m; }
+
+void dfs(Matrix &mat, int x, int y) {
+  Queue q;
+
+  q.push({x, y}), mat[x][y] = 2;
+  while (!q.empty()) {
+    auto [a, b] = q.front();
+    q.pop();
+    for (auto [oa, ob] : offsets) {
+      int x = a + oa, y = b + ob;
+      if (!valid(x, y) || mat[x][y] == 0 || mat[x][y] != 1) continue;
+      mat[x][y] = 2;
+      q.push({x, y});
+    }
+  }
+}