描述

在一个 n * m 的棋盘中(二维矩阵中 0 表示空 1 表示有障碍物)，骑士的初始位置是 (0, 0) ，他想要达到 (n - 1, m - 1) 这个位置，骑士只能从左边走到右边。找出骑士到目标位置所需要走的最短路径并返回其长度，如果骑士无法达到则返回 -1.

说明

如果骑士所在位置为(x,y)，那么他的下一步一步到达以下位置:
(x + 1, y + 2)
(x - 1, y + 2)
(x + 2, y + 1)
(x - 2, y + 1)

样例

[[0,0,0,0],
[0,0,0,0],
[0,0,0,0]]
返回 3
[[0,0,0,0],
[0,0,0,0],
[0,1,0,0]]
返回 -1

代码

public class Solution {
    /**
     * @param grid a chessboard included 0 and 1
     * @return the shortest path
     */
    public int shortestPath2(boolean[][] grid) {
        int n = grid.length;
        if (n == 0) {
            return -1;
        }
        
        int m = grid[0].length;
        if (m == 0) {
            return -1;
        }

        // f[m][n] 表示从起始位置到当前位置的最短路径长度
        int[][] f = new int[n][m];
        // 先假设 f 中的每个点不可达，设为 Integer.MAX_VALUE
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                f[i][j] = Integer.MAX_VALUE;
            }
        }

        f[0][0] = 0;
        // 从头到尾遍历所有结点，每个点对应的 f 值都要更新
        // f[i][j] 的结果受到 f[i–1][j–2]，f[i+1][j–2]，f[i–2][j–1]，f[i+2][j–1] 的影响
        // 因为每次都从左边往右跳，所以需要先算左边列的答案
        for (int j = 1; j < m; ++j) {
            for (int i = 0; i < n; ++i) {
                if (!grid[i][j]) {
                    // 除了边界点，对大多数点而言，有四个点可以到当前结点
                    // 判断条件满足 i 和 j 不越界，且当前结点的上一个位置不是不可达
                    // 即对应的 f 值不为 Integer.MAX_VALUE;
                    if (i >= 1 && j >= 2 && f[i - 1][j - 2] != Integer.MAX_VALUE) {
                        f[i][j] = Math.min(f[i][j], f[i - 1][j - 2] + 1);
                    }
                    if (i + 1 < n && j >= 2 && f[i + 1][j - 2] != Integer.MAX_VALUE) {
                        f[i][j] = Math.min(f[i][j], f[i + 1][j - 2] + 1);
                    }
                    if (i >= 2 && j >= 1 && f[i - 2][j - 1] != Integer.MAX_VALUE) {
                        f[i][j] = Math.min(f[i][j], f[i - 2][j - 1] + 1);
                    }
                    if (i + 2 < n && j >= 1 && f[i + 2][j - 1] != Integer.MAX_VALUE) {
                        f[i][j] = Math.min(f[i][j], f[i + 2][j - 1] + 1);
                    }
                }
            }
        }
        

        if (f[n - 1][m - 1] == Integer.MAX_VALUE) {
            return -1;
        }

        return f[n - 1][m - 1];
    }
}