[LintCode] Problem 611 - Knight Shortest Path

Posted on | In ,

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.

Note

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

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

No.1

Input:

1
2
3
[[0,0,0],
 [0,0,0],
 [0,0,0]]

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

Output: 2

Explanation:
[2,0]->[0,1]->[2,2]

No.2

Input:

1
2
3
[[0,1,0],
 [0,0,1],
 [0,0,0]]

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

Output: -1

Code

1
2
3
4
5
6
public class Point {
    int x;
    int y;
    Point() { x = 0; y = 0; }
    Point(int a, int b) { x = a; y = b; }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
public int shortestPath(boolean[][] grid, Point source, Point destination) {
    int result = 0;
    int n = grid.length;
    int m = grid[0].length;
    int[][] visited = new int[n][m];
    int[][] directions = {{1, 2}, {1, -2}, {-1, 2}, {-1, -2}, {2, 1}, {2, -1}, {-2, 1}, {-2, -1}};
    Queue<Point> queue = new LinkedList<>();

    queue.offer(source);
    visited[source.x][source.y] = 1;

    while (!queue.isEmpty()) {
        int size = queue.size();
        
        for (int i = 0; i < size; i++) {
            Point position = queue.poll();

            if (position.x == destination.x && position.y == destination.y)
                return result;

            for (int[] direction : directions) {
                int x = position.x + direction[0];
                int y = position.y + direction[1];

                if (x >= 0 && x < n && y >= 0 && y < m && grid[x][y] == false && visited[x][y] == 0) {
                    Point nextPos = new Point(x, y);
                    queue.offer(nextPos);
                    visited[x][y] = 1;
                }
            }
        }

        result++;
    }

    return -1;
}