leetcode

commit 59bb9742720b8a263fb022d83c6a0528d89ae729
parent ecc6491fcaa979b79eba0c6fa274e9d6f3e56379
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Fri, 10 Feb 2023 12:58:34 +0100

Daily Problem

Diffstat:
A
Problems/1162.cpp
 | 
40
++++++++++++++++++++++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 41 insertions(+), 0 deletions(-)
diff --git a/Problems/1162.cpp b/Problems/1162.cpp
@@ -0,0 +1,40 @@
+class Solution {
+  int n, m;
+
+  bool valid(int x, int y) { return x >= 0 && x < n && y >= 0 && y < m; }
+
+public:
+  int maxDistance(vector<vector<int>> &grid) {
+    n = grid.size(), m = grid[0].size();
+    queue<pair<int, int>> q;
+
+    for (int i = 0; i < n; i++) {
+      for (int j = 0; j < m; j++) {
+        if (grid[i][j]) {
+          q.push({i, j});
+          grid[i][j] = 0;
+        } else
+          grid[i][j] = -1;
+      }
+    }
+    if (q.empty() || q.size() == n * m) return -1;
+
+    vector<int> offset_x{0, 0, 1, -1}, offset_y{1, -1, 0, 0};
+
+    int res = 0;
+    while (!q.empty()) {
+      auto [a, b] = q.front();
+      q.pop();
+      res = max(res, grid[a][b]);
+      for (int i = 0; i < 4; i++) {
+        int x = a + offset_x[i];
+        int y = b + offset_y[i];
+        if (!valid(x, y) || grid[x][y] >= 0) continue;
+        grid[x][y] = grid[a][b] + 1;
+        q.push({x, y});
+      }
+    }
+
+    return res;
+  }
+};
diff --git a/README.md b/README.md
@@ -326,6 +326,7 @@ for solving problems.
 |  1129  |   Medium   | [Shortest Path with Alternating Colors](Problems/1129.cpp)                                       |
 |  1137  |    Easy    | [N-th Tribonacci Number](Problems/1137.cpp)                                                      |
 |  1143  |   Medium   | [Longest Common Subsequence](Problems/1143.cpp)                                                  |
+|  1162  |   Medium   | [As Far from Land as Possible](Problems/1162.cpp)                                                |
 |  1202  |   Medium   | [Smallest String With Swaps](Problems/1202.cpp)                                                  |
 |  1209  |   Medium   | [Remove All Adjacent Duplicates in String II](Problems/1209.cpp)                                 |
 |  1290  |    Easy    | [Convert Binary Number in a Linked List to Integer](Problems/1290.cpp)                           |