Knight Shortest Path

• Lintcode : 611 / Leetcode :
• Level : Medium

Problem

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.

Example
Example 1:

Input:
[[0,0,0],
 [0,0,0],
 [0,0,0]]
source = [2, 0] destination = [2, 2] 
Output: 2
Explanation:
[2,0]->[0,1]->[2,2]
Example 2:

Input:
[[0,1,0],
 [0,0,1],
 [0,0,0]]
source = [2, 0] destination = [2, 2] 
Output:-1
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)
Notice
source and destination must be empty.
Knight can not enter the barrier.
Path length refers to the number of steps the knight takes.

Concept & Algorithm

筆記

Time Complexity & Space Complexity

time : worst O(8 ^ step) / best O(8 ^ (step - 1))
space: O(m * n) (n = row, m = column)

Answer

/**
 * Definition for a point.
 * struct Point {
 *     int x;
 *     int y;
 *     Point() : x(0), y(0) {}
 *     Point(int a, int b) : x(a), y(b) {}
 * };
 */
class Solution {
vector<vector<int>> dir = {{1, 2}, {1 , -2}, {-1, 2}, {-1, -2}, {2, 1}, {2, -1}, {-2, 1}, {-2, -1}};
bool isValid(vector<vector<bool>> &grid, int r, int c) {
    if (r < 0 || c < 0 || r >= grid.size() || c >= grid[0].size() || grid[r][c]) return false;
    return true;
}
public:
    int shortestPath(vector<vector<bool>> &grid, Point &source, Point &destination) {
        if (grid.size() == 0 || grid[0].size() == 0) return -1;
        int n = grid.size(), m = grid[0].size();
        vector<vector<bool>> isVisited(n, vector<bool>(m, false));
        queue<Point> q;
        q.push(source);
        int step = 0;
        isVisited[source.x][source.y] = true;
        while (!q.empty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                Point p = q.front(); q.pop();
                if (p.x == destination.x && p.y == destination.y) return step;
                for(auto d : dir){
                    int row = d[0] + p.x;
                    int col = d[1] + p.y;
                    if (!isValid(grid, row, col) || isVisited[row][col]) continue;
                    q.push(Point(row, col));   
                    isVisited[row][col] = true;
                }
            }
            step++;
        }
        return -1;
    }

};

tags: BFS

​