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 || grid[0].length == 0 || grid[0][0]) return -1;
			
			int m = grid.length, n = grid[0].length;
			int[][] dp = new int[m][n];
		
			for (int i = 0; i < m; i++) {
				for (int j = 0; j < n; j++) {
					dp[i][j] = Integer.MAX_VALUE;
				}
			}
			dp[0][0] = 0; 
		//“dp[i][j] = Integer.MAX_VALUE” 已经相当于初始化了，所以不需要再每行每列初始化了
			int[][] dirs = {{-1, -2}, {1, -2}, {-2, -1}, {2, -1}}; //只能从左边转移过来
		
			for (int j = 0; j < n; j++) {
				for (int i = 0; i < m; i++) { //行走特性，需要按照每一列来算，反过来就会跳过某些格子
					if (!grid[i][j]) { //这个位置没有障碍 
						for (int k = 0; k < 4; k++) {
							int x = i + dirs[k][0], y = j + dirs[k][1];
							if (x >= 0 && x < m && y >= 0 && y < n && dp[x][y] !=
		Integer.MAX_VALUE) { //判断[x][y] 能否到达
			dp[i][j] = Math.min(dp[x][y] + 1, dp[i][j]);
		}
						}
					}
				}
			}
			return dp[m - 1][n - 1] == Integer.MAX_VALUE ? -1 : dp[m - 1][n - 1];
		}
}