diff options
Diffstat (limited to 'shortest_path_binary_matrix.cpp')
-rw-r--r-- | shortest_path_binary_matrix.cpp | 45 |
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 +} |