java - 使用两次遍历收集网格中的最大点

Question

我有一个2D矩阵，我从单元格0,0出发，并使用以下方法从矩阵中收集尽可能多的1:
每个单元格可以具有值0，1，-1

0 means a path is present
1 means I can collect this as point
-1 means an obstruction

以下是要遵循的规则:

从(0,0)开始直到终点(n-1，n-1)。向终点移动
右->或下->通过有效单元格(表示具有0或1的单元格)

到达(m-1，n-1)后，向左移动<-或向上移动回到(0,0)
通过有效的单元格。

在旅行时选择全1，并将其设为空单元格(0值)

通过遵循这种方法，可以收集尽可能多的1。

Example:

0 1 1
1 0 1
1 1 1

Output:
7

Explanation:

(0,0) -> (0,1) -> (0,2) -> (1,2) -> (2,2) ->
Now reverse direction
(2,2) -> (2,1) -> (2,0) -> (1,0) -> (0,0)

Using this path I can collect 7 ones. so result is 7.

=================

Example:

0 1 1
1 0 -1
1 1 -1

Output:
0

Explanation:

Cell (2,2) is blocked, so we cannot collect any ones 

我想出了下面不完整的代码，该代码遵循步骤1的意思是从(0,0)到终点

class Main {
    // Function to check if cell (i, j) is valid and safe to visit
    public static boolean isSafe(int[][] mat, int i, int j) {
        if (i < 0 || i >= mat.length || j < 0 || j >= mat[0].length || mat[i][j] == -1) {
            return false;
        }

        return true;
    }

    // Function to collect maximum number of ones starting from
    // cell mat[i][j]
    public static int findMaximum(int[][] mat, int i, int j) {
        // return if cell (i, j) is invalid or unsafe to visit
        if (!isSafe(mat, i, j)) {
            return 0;
        }
        int max = Integer.max(findMaximum(mat, i, j + 1), findMaximum(mat, i + 1, j));
        max += mat[i][j];
        mat[i][j] = 0;// making it empty cell
        return max;
    }

    public static void main(String[] args) {
        int[][] mat = { { 0, 1, 1 }, { 1, 0, 1 }, { 1, 1, 1 } };// 7

        System.out.println(findMaximum(mat, 0, 0));
    }
}

程序输出4而不是7。您能帮我解决此任务的正确方法是什么？

Answer 1

请注意，找到从(i，j)到(n-1，n-1)的路径与找到从(n-1，n-1)到(i，j)的路径相同。
同样，找到从(0，0)到(n-1，n-1)然后回到(0，0)的路径等效于找到从(0，0)到(n-1，n- 1)，前提是我们不重新计算两条路径的点数。
为了防止这种重新计数，我们可以按照以下伪代码所示的锁定步骤从两条路径中找到点:

# (i1, j1) and (i2, j2) is the current location in the first and second path respectively.
def points(i1, j1, i2, j2):
    if not is_safe(i1, j1) or not is_safe(i2, j2):
        return float("-inf")
    if (i1, j1) == (i2, j2) == (n-1, n-1):
        return m[i1][j1]

    # Notice we don't double count the value if the paths cross.
    if (i1, j1) == (i2, j2):
        num_points = m[i1][j1]
    else:
        num_points = m[i1][j1] + m[i2][j2]

    return num_points + max(
        points(i1+1, j1, i2+1, j2), # Both paths go down.
        points(i1, j1+1, i2, j2+1), # Both paths go right.
        points(i1+1, j1, i2, j2+1), # First path path goes down, second goes right.
        points(i1, j1+1, i2+1, j2), # First path path goes right, second goes down.
    )

由于将存在重复的子计算，因此，如果我们缓存此函数，则应给出多项式时间算法。
该算法花费O(N^3)时间，即使矩阵包含大于1的点，也会找到最佳解。
带有Java实现的Here is a repl。