aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2024-11-28 21:08:23 -0700
committerJack Sangdahl <[email protected]>2024-11-28 21:08:23 -0700
commit4e7f851984f894d78ebb75465b60989967e3421a (patch)
tree3283de7af1dc216915425d2f03de5a33f153c494
parentb7a4721387ecac2e6de1eab85c2d2ab9cd8c5c5e (diff)
downloadleetcode-4e7f851984f894d78ebb75465b60989967e3421a.tar.gz
leetcode-4e7f851984f894d78ebb75465b60989967e3421a.zip
2577. minimum time to visit a cell in a grid
-rw-r--r--min_time_visit_cell_grid.cpp52
-rw-r--r--min_time_visit_cell_grid.py44
2 files changed, 96 insertions, 0 deletions
diff --git a/min_time_visit_cell_grid.cpp b/min_time_visit_cell_grid.cpp
new file mode 100644
index 0000000..ce982b5
--- /dev/null
+++ b/min_time_visit_cell_grid.cpp
@@ -0,0 +1,52 @@
+// 2577. Minimum Time to Visit a Cell In a Grid
+#include "leetcode.h"
+
+/*
+ * you are given an 'm x n' matrix 'grid' consisting of non-negative integers
+ * where 'grid[row][col]' represents the minimum time required to be able to
+ * visit the cell '(row, col)', which means you can visit the cell '(row, col)'
+ * only when the time you visit it is greater than or equal to the value. you
+ * are standing in the top left cell of the matrix in the 0th second and you
+ * must move to any adjacent cell in the four directions: up, down, left, and
+ * right. each move you make takes 1 second. return the minimum time required in
+ * which you can visit the bottom right cell of the matrix. if you cannot visit
+ * the bottomright cell, then return -1.
+ */
+
+class Solution {
+public:
+ int minimumTime(vector<vector<int>> &grid) {
+ if (grid[0][1] > 1 && grid[1][0] > 1)
+ return -1;
+ int m = grid.size(), n = grid[0].size();
+ vector<vector<int>> dir = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
+ vector<vector<bool>> vis(m, vector<bool>(n, false));
+ priority_queue<vector<int>, vector<vector<int>>, greater<>> pq;
+ pq.push({grid[0][0], 0, 0});
+ while (!pq.empty()) {
+ int time = pq.top()[0], row = pq.top()[1], col = pq.top()[2];
+ pq.pop();
+ if (row == m - 1 && col == n - 1)
+ return time;
+ if (vis[row][col])
+ continue;
+ vis[row][col] = true;
+ for (auto i : dir) {
+ int r = row + i[0], c = col + i[1];
+ if (r < 0 || r >= m || c < 0 || c >= n || vis[r][c])
+ continue;
+ int wait = !((grid[r][c] - time) % 2);
+ pq.push({max(grid[r][c] + wait, time + 1), r, c});
+ }
+ }
+ return -1;
+ }
+};
+
+int main() {
+ Solution obj;
+ vvd(int) g1 = {{0, 1, 3, 2}, {5, 1, 2, 5}, {4, 3, 8, 6}},
+ g2 = {{0, 2, 4}, {3, 2, 1}, {1, 0, 4}};
+ printf("%d\n", obj.minimumTime(g1)); // expect: 7
+ printf("%d\n", obj.minimumTime(g2)); // expect: -1
+}
diff --git a/min_time_visit_cell_grid.py b/min_time_visit_cell_grid.py
new file mode 100644
index 0000000..aab6075
--- /dev/null
+++ b/min_time_visit_cell_grid.py
@@ -0,0 +1,44 @@
+# 2577. Minimum Time to Visit a Cell In a Grid
+import heapq
+
+"""
+you are given an 'm x n' matrix 'grid' consisting of non-negative integers
+where 'grid[row][col]' represents the minimum time required to be able to
+visit the cell '(row, col)', which means you can visit the cell '(row, col)'
+only when the time you visit it is greater than or equal to the value. you
+are standing in the top left cell of the matrix in the 0th second and you
+must move to any adjacent cell in the four directions: up, down, left, and
+right. each move you make takes 1 second. return the minimum time required in
+which you can visit the bottom right cell of the matrix. if you cannot visit
+the bottomright cell, then return -1.
+"""
+
+
+class Solution(object):
+ def minimumTime(self, grid):
+ """
+ :type grid: List[List[int]]
+ :rtype: int
+ """
+ if grid[0][1] > 1 and grid[1][0] > 1:
+ return -1
+ m, n = len(grid), len(grid[0])
+ vis, pq = set(), [(grid[0][0], 0, 0)]
+ while pq:
+ time, row, col = heapq.heappop(pq)
+ if row == m - 1 and col == n - 1:
+ return time
+ if (row, col) in vis:
+ continue
+ vis.add((row, col))
+ for dr, dc in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
+ r, c = row + dr, col + dc
+ if 0 <= r < m and 0 <= c < n and (r, c) not in vis:
+ wait = 1 if ((grid[r][c] - time) % 2 == 0) else 0
+ heapq.heappush(pq, (max(time + 1, grid[r][c] + wait), r, c))
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.minimumTime(grid=[[0, 1, 3, 2], [5, 1, 2, 5], [4, 3, 8, 6]]))
+ print(obj.minimumTime(grid=[[0, 2, 4], [3, 2, 1], [1, 0, 4]]))