class Solution {
using Index = pair<int, int>;
vector<Index> directions =
{
{-1, -1},
{-1, 0},
{-1, 1},
{0, -1},
{0, 1},
{1, -1},
{1, 0},
{1, 1}
};
public:
int shortestPathBinaryMatrix(vector<vector<int>>& grid)
{
const int n = grid.size();
if (grid[0][0] == 1 || grid[n - 1][n - 1] == 1)
return -1;
if (n == 1)
return 1;
int distance = 1;
Index target = {n - 1, n - 1};
queue<Index> q;
q.push({0, 0});
grid[0][0] = 1;
while (!q.empty())
{
const int levelSize = q.size();
for (int i = 0; i < levelSize; i++)
{
Index curr = q.front();
q.pop();
for (const Index& diff : directions)
{
Index next = {curr.first + diff.first, curr.second + diff.second};
if (next.first >= 0 && next.first < n && next.second >= 0 && next.second < n
&& grid[next.first][next.second] == 0)
{
if (next == target)
return distance + 1;
grid[next.first][next.second] = 1;
q.push(next);
}
}
}
distance++;
}
return -1;
}
};