leetcode

commit d637f07e6e8ba2c95b64b031e61cbfd174566213
parent 29b4ccbac9b809e267bdb349f454140b95f3b12f
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Tue, 24 Jan 2023 13:31:17 +0100

Daily Problem

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

2 files changed, 41 insertions(+), 0 deletions(-)
diff --git a/Problems/0909.cpp b/Problems/0909.cpp
@@ -0,0 +1,40 @@
+class Solution {
+public:
+  int snakesAndLadders(vector<vector<int>> &board) {
+    const int n = board.size();
+
+    // index directy with a square instead of a coordinate
+    vector<int> cord(n * n + 1);
+
+    int crnt = 1, x = n - 1, y = 0, dir = 1;
+    while (crnt <= n * n) {
+      cord[crnt] = board[x][y];
+      if (crnt % n == 0)
+        x--, dir *= -1;
+      else
+        y += dir;
+      crnt++;
+    }
+
+    vector<bool> visited(n * n + 1);
+    queue<pair<int, int>> q;
+    int res = INT_MAX;
+
+    q.push({1, 0}), visited[1] = true;
+    while (!q.empty()) {
+      auto [crnt, move] = q.front();
+      q.pop();
+
+      if (crnt == n * n) return move;
+
+      for (int i = 0; i < 6; i++) {
+        if (++crnt > n * n) break;
+        int square = cord[crnt] == -1 ? crnt : cord[crnt];
+        if (visited[square]) continue;
+        visited[square] = true;
+        q.push({square, move + 1});
+      }
+    }
+    return -1;
+  }
+};
diff --git a/README.md b/README.md
@@ -220,6 +220,7 @@ for solving problems.
 |  0897  |    Easy    | [Increasing Order Search Tree](Problems/0897.cpp)                                                |
 |  0901  |   Medium   | [Online Stock Span](Problems/0901.cpp)                                                           |
 |  0905  |    Easy    | [Sort Array By Parity](Problems/0905.cpp)                                                        |
+|  0909  |   Medium   | [Snakes and Ladders](Problems/0909.cpp)                                                          |
 |  0918  |   Medium   | [Maximum Sum Circular Subarray](Problems/0918.cpp)                                               |
 |  0926  |   Medium   | [Flip String to Monotone Increasing](Problems/0926.cpp)                                          |
 |  0931  |   Medium   | [Minimum Falling Path Sum](Problems/0931.cpp)                                                    |