[LintCode] Problem 630 - Knight Shortest Path II

Posted on | In ,

Given a knight in a chessboard n * 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 -1 if knight can not reached.

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

No.1

Input:
[[0,0,0,0],[0,0,0,0],[0,0,0,0]]

Output:
3

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

No.2

Input:
[[0,1,0],[0,0,1],[0,0,0]]

Output:
-1

Code

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
public int shortestPath2(boolean[][] grid) {
    int n = grid.length;
    int m = grid[0].length;
    int[][] visited = new int[n][m];
    int[][] directions = {{1, 2}, {-1, 2}, {2, 1}, {-2, 1}};
    Queue<int[]> queue = new LinkedList<>();

    queue.offer(new int[] {0, 0, 0});
    visited[0][0] = 1;

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

            if (position[0] == n - 1 && position[1] == m - 1)
                return position[2];

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

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

    return -1;
}