Description
Given a knight in a chessboard (a binary matrix with 0 as empty and 1 as barrier) with a source position, find the shortest path to a destination position, return the length of the route.
Return -1 if destination cannot be reached.
Answer
Using BFS to solve the problem. Set a vector d to optimize the search method of each nonzero point. Using queue to store all the points of each layer at once.
Code
C++
class Solution {
public:
/**
* Definition for a point.
* struct Point {
* int x;
* int y;
* Point() : x(0), y(0) {}
* Point(int a, int b) : x(a), y(b) {}
* };
*/
int shortestPath(vector<vector<bool>> &grid, Point &source, Point &destination) {
// write your code here
if(grid.size() == 0 || grid[0].size() == 0) return 0;
int n = grid.size(), m = grid[0].size();
vector<vector<int>> dis(n, vector<int>(m, INT_MAX));
dis[source.x][source.y] = 0;
vector<vector<int>> d = {{-2, -1}, {-2, 1}, {-1, 2}, {1, 2}, {2, 1}, {2, -1}, {1, -2}, {-1, -2}};
std::queue<Point> q;
q.push(source);
while(!q.empty())
{
Point head = q.front();
q.pop();
for(int i = 0; i < 8; ++i)
{
int x = head.x + d[i][0];
int y = head.y + d[i][1];
if(x >= 0 && x < n && y >= 0 && y < m && !grid[x][y] && dis[head.x][head.y] + 1 < dis[x][y])
{
dis[x][y] = dis[head.x][head.y] + 1;
q.push(Point(x, y));
}
}
}
if(dis[destination.x][destination.y] == INT_MAX) return -1;
return dis[destination.x][destination.y];
}
};
