aboutsummaryrefslogtreecommitdiff
path: root/shortest_path_binary_matrix.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'shortest_path_binary_matrix.cpp')
-rw-r--r--shortest_path_binary_matrix.cpp45
1 files changed, 30 insertions, 15 deletions
diff --git a/shortest_path_binary_matrix.cpp b/shortest_path_binary_matrix.cpp
index 67cd095..cbdccdc 100644
--- a/shortest_path_binary_matrix.cpp
+++ b/shortest_path_binary_matrix.cpp
@@ -1,40 +1,55 @@
+// 1091. Shortest Path in Binary Matrix
#include "leetcode.h"
-#include <algorithm>
-#include <queue>
-#include <utility>
-#include <vector>
+
+/*
+ * given an n x n binary matrix 'grid', return the length of the shortest clear
+ * path in the matrix. if there is no clear path, return -1. a clear path in a
+ * binary matrix is a path from the top-left cell (ie. 0,0) to the bottom-right
+ * cell (ie. n - 1, n - 1) such thatyt
+ * - all the visited cells are of the path 0
+ * - all the adjacent cells of the path are 8-directionally connected (ie. they
+ * are different and they share an edge of a corner) the length of a clear path
+ * is the number of visited cells of this path
+ */
class Solution {
public:
int shortestPathBinaryMatrix(vector<vector<int>> &grid) {
if (grid[0][0] || grid.back().back())
return -1;
- int ans = 2, len = 1, nX = grid[0].size() - 1, nY = grid.size() - 1;
+ int ans = 2, n = 1, nr = grid[0].size() - 1, nc = grid.size() - 1;
queue<pair<int, int>> qp;
- if (!nX && !nY)
+ if (!nr && !nc)
return 1 - (grid[0][0] << 1);
qp.push({0, 0});
grid[0][0] = -1;
- while (len) {
- while (len--) {
- auto [cX, cY] = qp.front();
+ while (n) {
+ while (n--) {
+ auto [cx, cy] = qp.front();
qp.pop();
- for (int i = max(0, cX - 1), lmtX = min(cX + 1, nX); i <= lmtX; i++) {
- for (int j = max(0, cY - 1), lmtY = min(cY + 1, nY); j <= lmtY; j++) {
- if (i == nX && j == nY)
+ for (int i = max(0, cx - 1), lmtx = min(cx + 1, nr); i <= lmtx; i++)
+ for (int j = max(0, cy - 1), lmty = min(cy + 1, nc); j <= lmty; j++) {
+ if (i == nr && j == nc)
return ans;
if (!grid[j][i]) {
grid[j][i] = -1;
qp.push({i, j});
}
}
- }
}
ans++;
- len = qp.size();
+ n = qp.size();
}
return -1;
}
};
-int main() {}
+int main() {
+ Solution obj;
+ vvd(int) g1 = {{0, 1}, {1, 0}};
+ vvd(int) g2 = {{0, 0, 0}, {1, 1, 0}, {1, 1, 0}};
+ vvd(int) g3 = {{1, 0, 0}, {1, 1, 0}, {1, 1, 0}};
+ printf("%d\n", obj.shortestPathBinaryMatrix(g1)); // expect: 2
+ printf("%d\n", obj.shortestPathBinaryMatrix(g2)); // expect: 4
+ printf("%d\n", obj.shortestPathBinaryMatrix(g3)); // expect: -1
+}