9月21日机考第三题动态规划，加第二题兵马寻路

```class Solution {
    /*
     * 在路边中一批树，每棵树能种的位置和树冠半径是固定的，
     * 两棵树的树冠不能重叠，每棵树有一个美观值，求使得美观值最大的种法*/
    public int plantTrees(int n, int[] trees, int[] radius, int[] values) {
        int[][] dp = new int[n][2];
        int[] rights = new int[n];
        int max = values[0];
        dp[0][0] = 0;
        dp[0][1] = values[0];
        rights[0] = trees[0] + radius[0];
        for (int i = 1; i < n; i++) {
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1]);
            int pos = i, left = trees[i] - radius[i];
            while (pos > 0) {
                if (rights[pos - 1] <= left) break;
                else pos--;
            }
            dp[i][1] = dp[pos][0] + values[i];
            rights[i] = trees[i] + radius[i];
            max = Math.max(Math.max(dp[i][0], dp[i][1]), max);
        }
        return max;
    }
}

class Solution {
    public int soldierMove(char[][] board, int[] target) {
        int[][] infantry = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}},
                cavalry = {{-2, -1}, {-2, 1}, {2, -1}, {2, 1}, {-1, -2}, {1, -2}, {-1, 2}, {1, 2}};
        int m = board.length, n = board[0].length;
        boolean[][][] visited = new boolean[m][n][2];
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{0, 0, 0, 0});
        visited[0][0][0] = true;
        if (board[0][0] == 'S') {
            queue.offer(new int[]{0, 0, 1, 1});
            visited[0][0][1] = true;
        }
        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            int row = cur[0], col = cur[1], type = cur[2], way = cur[3];
            int[][] dirs = type == 0 ? infantry : cavalry;
            for (int[] dir : dirs) {
                int nr = row + dir[0], nc = col + dir[1];
                if (nr < 0 || nr >= m || nc < 0 || nc >= n || board[nr][nc] == 'X') continue;
                if (nr == target[0] && nc == target[1]) {
                    return way + 1;
                }
                if (board[nr][nc] == 'S') {
                    for (int i = 0; i < 2; i++) {
                        if (!visited[nr][nc][i]) {
                            queue.offer(new int[]{nr, nc, i, way + (type == i ? 1 : 2)});
                            visited[nr][nc][i] = true;
                        }
                    }
                } else {
                    if (!visited[nr][nc][type]) {
                        queue.offer(new int[]{nr, nc, type, way + 1});
                        visited[nr][nc][type] = true;
                    }
                }
            }
        }
        return -1;
    }
}