-
Notifications
You must be signed in to change notification settings - Fork 0
/
1091. Shortest Path in Binary Matrix.cpp
64 lines (50 loc) · 1.75 KB
/
1091. Shortest Path in Binary Matrix.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
// https://leetcode.com/problems/shortest-path-in-binary-matrix/
class Solution
{
public:
int shortestPathBinaryMatrix(vector<vector<int>> &grid)
{
if (grid[0][0] == 1 || grid[grid.size() - 1][grid[0].size() - 1] == 1)
return -1;
if (grid.size() == 1)
return 1;
int result = 1;
queue<pair<int, int>> nodes;
vector<vector<int>> directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}, {-1, -1}, {1, 1}, {-1, 1}, {1, -1}};
nodes.push({0, 0});
grid[0][0] = 2;
while (!nodes.empty())
{
result++;
int size = nodes.size();
for (int i = 0; i < size; ++i)
{
pair<int, int> node = nodes.front();
nodes.pop();
int row = node.first;
int column = node.second;
for (vector<int> &direction : directions)
{
int newRow = row + direction[0];
int newColumn = column + direction[1];
if (!isValidPosition(grid, newRow, newColumn))
continue;
if (newRow == grid.size() - 1 && newColumn == grid[newRow].size() - 1 && grid[newRow][newColumn] == 0)
return result;
if (grid[newRow][newColumn] == 0)
{
nodes.push({newRow, newColumn});
grid[newRow][newColumn] = 2;
}
}
}
}
return -1;
}
bool isValidPosition(vector<vector<int>> &grid, int i, int j)
{
if (i >= grid.size() || i < 0 || j >= grid[i].size() || j < 0)
return false;
return true;
}
};