# 1091. Shortest Path in Binary Matrix

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 (i.e., `(0, 0)`) to the bottom-right cell (i.e., `(n - 1, n - 1)`) such that:

• All the visited cells of the path are `0`.
• All the adjacent cells of the path are 8-directionally connected (i.e., they are different and they share an edge or a corner).

The length of a clear path is the number of visited cells of this path.

Example 1:

``````Input: grid = [[0,1],[1,0]]
Output: 2
``````

Example 2:

``````Input: grid = [[0,0,0],[1,1,0],[1,1,0]]
Output: 4
``````

Example 3:

``````Input: grid = [[1,0,0],[1,1,0],[1,1,0]]
Output: -1
``````

Constraints:

• `n == grid.length`
• `n == grid[i].length`
• `1 <= n <= 100`
• `grid[i][j] is 0 or 1`

``````class Solution {
public:
int shortestPathBinaryMatrix(vector<vector<int>>& grid) {
if (grid[0][0] == 1) return -1;
int res = 0, n = grid.size();
set<vector<int>> visited;
visited.insert({0, 0});
queue<vector<int>> q;
q.push({0, 0});
vector<vector<int>> dirs{{-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}, {-1, -1}};
while (!q.empty()) {
++res;
for (int i = q.size(); i > 0; --i) {
auto t = q.front(); q.pop();
if (t[0] == n - 1 && t[1] == n - 1) return res;
for (auto dir : dirs) {
int x = t[0] + dir[0], y = t[1] + dir[1];
if (x < 0 || x >= n || y < 0 || y >= n || grid[x][y] == 1 || visited.count({x, y})) continue;
visited.insert({x, y});
q.push({x, y});
}
}
}
return -1;
}
};
``````

Github 同步地址:

https://github.com/grandyang/leetcode/issues/1091

https://leetcode.com/problems/shortest-path-in-binary-matrix/

https://leetcode.com/problems/shortest-path-in-binary-matrix/discuss/312706/JAVA-BFS

https://leetcode.com/problems/shortest-path-in-binary-matrix/discuss/313347/A*-search-in-Python

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation