Given a knight in a chessboard (a binary matrix with0as empty and1as barrier) with asourceposition, find the shortest path to adestinationposition, return the length of the route.
Return-1if knight can not reached.

Notice

source and destination must be empty.
Knight can not enter the barrier.

Have you met this question in a real interview?

Yes

Clarification

If the knight is at (x,y), he can get to the following positions in one step:

(x + 1, y + 2)
(x + 1, y - 2)
(x - 1, y + 2)
(x - 1, y - 2)
(x + 2, y + 1)
(x + 2, y - 1)
(x - 2, y + 1)
(x - 2, y - 1)

Example

[[0,0,0],
 [0,0,0],
 [0,0,0]]
source = [2, 0] destination = [2, 2] return 2

[[0,1,0],
 [0,0,0],
 [0,0,0]]
source = [2, 0] destination = [2, 2] return 6

[[0,1,0],
 [0,0,1],
 [0,0,0]]
source = [2, 0] destination = [2, 2] return -1

/**
 * Definition for a point.
 * struct Point {
 *     int x, y;
 *     Point() : x(0), y(0) {}
 *     Point(int a, int b) : x(a), y(b) {}
 * };
 */
class Solution {
public:
    /**
     * @param grid a chessboard included 0 (false) and 1 (true)
     * @param source, destination a point
     * @return the shortest path 
     */
    int shortestPath(vector<vector<bool>>& grid, Point& source, Point& destination) {
        // Write your code here
        if (grid.empty() || grid[0].empty())
            return -1;
        int n = grid.size(), m = grid[0].size();
        queue<Point> q;
        auto cmp = [=](const Point& left, const Point& right) {
            return left.x * m + left.y < right.x * m + right.y;
        };
        set<Point, decltype(cmp)> points(cmp);
        int step = 0;
        q.push(source);
        points.insert(source);

        vector<vector<int>> dirs = { {1, 2}, {1, -2}, {-1, 2}, {-1, -2}, {2, 1},
                                     {2, -1}, {-2, 1}, {-2, -1}};
        while (!q.empty()) {
            int size = q.size();
            for (int i = 0; i < size; ++i)  {
                Point pt = q.front(); q.pop();
                if (pt.x == destination.x && pt.y == destination.y)
                    return step;
                for (const auto& dir : dirs) {
                    int nx = pt.x + dir[0];
                    int ny = pt.y + dir[1];
                    Point nPt(nx, ny);
                    if ( nx >= 0 && nx < n && ny >= 0 && ny < m &&
                        grid[nPt.x][nPt.y] == 0 &&
                        points.find(nPt) == points.end()) {
                            q.push(nPt);
                            points.insert(nPt);
                        }
                }
            }
            ++step;
        }

        return -1;
    }
};