Given a knight in a chessboardn * m(a binary matrix with 0 as empty and 1 as barrier). the knight initialze position is(0, 0)and he wants to reach position(n - 1, m - 1), Knight can only be from left to right. Find the shortest path to the destination position, return the length of the route. Return-1if knight can not reached.

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 + 2, y + 1)
(x - 2, y + 1)

Example

[[0,0,0,0],
 [0,0,0,0],
 [0,0,0,0]]

Return 3

[[0,0,0,0],
 [0,0,0,0],
 [0,1,0,0]]

Return -1

class Solution {
public:
    /**
     * @param grid a chessboard included 0 and 1
     * @return the shortest path
     */
    int shortestPath2(vector<vector<bool>>& grid) {
        // Write your code here
        vector<vector<int>> f;
        if (grid.empty() || grid[0].empty()) {
            return -1;
        }
        int n = grid.size(), m = grid[0].size();
        f.resize(n, vector<int>(m, INT_MAX));
        queue<pair<int, int>> q;
        q.push(make_pair(0, 0));
        int step = 0;
        vector<vector<int>> offsets = {{1,2}, {-1,2}, {2,1}, {-2, 1}};
        while (!q.empty()) {
            int size = q.size();
            for (int i = 0; i < size; ++i) {
                auto cur = q.front();
                q.pop();
                f[cur.first][cur.second] = step;
                if (grid[cur.first][cur.second] > 0) {
                    continue;
                }
                for (auto &offset : offsets) {
                    int nx = cur.first + offset[0];
                    int ny = cur.second + offset[1];
                    if (nx >= 0 && nx < n && ny >= 0 && ny < m
                        && f[nx][ny] == INT_MAX) {
                          q.push(make_pair(nx, ny));
                        }
                }    
            }
            ++step;
        }

        if (f[n - 1][m - 1] == INT_MAX) {
            return -1;
        }
        return f[n - 1][m - 1];
    }
};