LeetCode-1091. Shortest Path in Binary Matrix

LeetCode-1091. Shortest Path in Binary Matrix

In an N by N square grid, each cell is either empty (0) or blocked (1).

A clear path from top-left to bottom-right has length ​​k​​​ if and only if it is composed of cells ​​C_1, C_2, ..., C_k​​ such that:

Adjacent cells​​C_i​​​ and​​C_{i+1}​​ are connected 8-directionally (ie., they are different and share an edge or corner)​​C_1​​​ is at location​​(0, 0)​​​ (ie. has value​​grid[0][0]​​)​​C_k​​​ is at location​​(N-1, N-1)​​​ (ie. has value​​grid[N-1][N-1]​​)If​​C_i​​​ is located at​​(r, c)​​​, then​​grid[r][c]​​​ is empty (ie.​​grid[r][c] == 0​​).

Return the length of the shortest such clear path from top-left to bottom-right.  If such a path does not exist, return -1.

Example 1:

Input: [[0,1],[1,0]]Output: 2

Example 2:

Input: [[0,0,0],[1,1,0],[1,1,0]]Output: 4

Note:

​​1 <= grid.length == grid[0].length <= 100​​​​grid[r][c]​​​ is​​0​​​ or​​1​​

题解：

dfs会搜索很多重复路径，使用bfs搜索最短路径。

最短路径第一时间想到bfs。

三元组效率低一些：

class Solution {public: int shortestPathBinaryMatrix(vector>& grid) { if (grid.empty() == true) { return -1; } int n = grid.size(), m = grid[0].size(), res = 10000; if (grid[0][0] == 1 || grid[n - 1][m - 1] == 1) { return -1; } queue> q; q.push({0, 0, 1}); int d[8][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}, {-1, -1}, {-1, 1}, {1, -1}, {1, 1}}; while (q.empty() == false) { vector tmp = q.front(); q.pop(); if (tmp[0] == n - 1 && tmp[1] == m - 1) { res = min(res, tmp[2]); } if (tmp[2] > res) { continue; } for (int i = 0; i < 8; i++) { int x = tmp[0] + d[i][0]; int y = tmp[1] + d[i][1]; if (x >= 0 && x < n && y >= 0 && y < m && grid[x][y] == 0) { grid[x][y] = 1; q.push({x, y, tmp[2] + 1}); } } } if (res == 10000) { return -1; } return res; }};

使用pair加ans存储高效：

class Solution {public: int shortestPathBinaryMatrix(vector>& grid) { if (grid.empty() == true) { return -1; } int n = grid.size(), m = grid[0].size(); if (grid[0][0] == 1 || grid[n - 1][m - 1] == 1) { return -1; } queue> q; q.push({0, 0}); int ans = 1; int d[8][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}, {-1, -1}, {-1, 1}, {1, -1}, {1, 1}}; while (q.empty() == false) { int len = q.size(); for (int i = 0; i < len; i++) { pair tmp = q.front(); q.pop(); if (tmp.first == n - 1 && tmp.second == m - 1) { return ans; } for (int i = 0; i < 8; i++) { int x = tmp.first + d[i][0]; int y = tmp.second + d[i][1]; if (x >= 0 && x < n && y >= 0 && y < m && grid[x][y] == 0) { grid[x][y] = 1; q.push({x, y}); } } } ans++; } return -1; }};

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。