Knight Shortest Path II

Java

public class Solution {
    /**
     * @param grid: a chessboard included 0 and 1
     * @return: the shortest path
     */
			public int shortestPath2(boolean[][] grid) {
					if (grid == null || grid.length == 0) return -1;
					int m = grid.length;
					int n = grid[0].length;
					if (grid[0][0] || grid[m - 1][n - 1]) return -1;
					if (m == 1 && n == 1) return 0;
			
					Queue<Integer> qA = new LinkedList<>();
					boolean[][] vA = new boolean[m][n];
					qA.offer(0);
					vA[0][0] = true;
			
					Queue<Integer> qB = new LinkedList<>();
					boolean[][] vB = new boolean[m][n];
					qB.offer(m * n - 1);
					vA[m - 1][n - 1] = true;
			
					Queue<Integer> que = null;
					boolean[][] vCur = null, vOp = null;
					
					int result = 0, sign = 0;
					
					int[] dx = {-1, 1, -2, 2};
					int[] dy = {2, 2, 1, 1};
					
					while (!qA.isEmpty() && !qB.isEmpty()) {
						if (qA.size() <= qB.size()) {
							que = qA;
							vCur = vA;
							vOp = vB;
							sign = 1;
						} else {
							que = qB;
							vCur = vB;
							vOp = vA;
							sign = -1;	
						}
						result++;
						int size = que.size();
					
						while (size-- != 0) {
						int cur = que.poll();
						int cx = cur / n, cy = cur % n;
						for (int i = 0; i < 4; i++) {
							int nx = cx + sign * dx[i], ny = cy + sign * dy[i];
							if (nx >= 0 && nx < m && ny >= 0 && ny < n && !grid[nx][ny]) {
								if (vOp[nx][ny]) return result;
								if (!vCur[nx][ny]) {
									que.offer(nx * n + ny);
									vCur[nx][ny] = true;
								}
							}	
						}
					}
					}
					return -1;
				}
}