Coursera Algorithm Ⅱ week2 编程作业 Seam Carving

最近时间管理有点问题，直接贴代码了（逃

地址：

dp做的，主要就是找二维的最短路径，功能分都拿到了，好像还可以再优化一下

class Solution {
    // 就是遍历A，然后每个为1的，看他能不能通过移动离开跳出A
    // 不能跳出的basecase是什么？
    private int[][] A;
    private int[] drow = {-1, 1, 0, 0};
    private int[] dcol = {0, 0, -1, 1};
    private boolean[][] marked;

    private boolean outOfbound(int row, int col) {
        return row < 0 || row >= A.length || col < 0 || col >= A[0].length;
    }

    private boolean canGetOut(int row, int col) {
        if (outOfbound(row, col)) {
            return true;
        }
        if (marked[row][col] == true) {
            return false;
        }
        marked[row][col] = true;
        boolean rs = false;
        for (int i = 0; i < 4; i++) {
            int tRow = row + drow[i];
            int tCol = col + dcol[i];
            if (!outOfbound(tRow, tCol) && A[tRow][tCol] == 0) {
                continue;
            }
            rs = rs || canGetOut(tRow, tCol);
        }
        return rs;
    }

    public int numEnclaves(int[][] A) {
        int count = 0;
        this.A = A;
        for (int i = 0; i < A.length; i++) {
            for (int j = 0; j < A[0].length; j++) {
                if (A[i][j] == 0) {
                    continue;
                }
                marked = new boolean[A.length][A[0].length];
                if (!canGetOut(i, j)) {
                    count++;
                }
            }
        }
        return count;
    }

    public static void main(String[] args) {
        int[][] A = {{0, 0, 0, 0}, {1, 0, 1, 0}, {0, 1, 1, 0}, {0, 0, 0, 0}};
        System.out.println(new Solution().numEnclaves(A));
    }
}