使用递归解决矩阵问题时得到错误答案

Question

问题是：给定具有随机 (0, 1) 值的 mXn 矩阵。从最开始的位置开始向 m-1, n-1 位置（最后位置）移动，我们唯一可以移动的方向是向下或向右。

规则：

如果找到 1 个无法移动
唯一可能的移动是0 所以找到可能到达(m-1,n-1)位置的方法。

示例：矩阵（（0、0、0）、（0、0、0）、（0、0、0））答案：6

这是我的逻辑：

public class Main {
    static int possibility = 0;
    static int r = 3;
    static int c = 3;
    public static void main(String[] args) {
        int array[][] = {{0, 0, 0}, {0, 0, 0}, {0, 0, 0}};
        // int array[][] = {{0, 1, 1}, {0, 0, 1}, {1, 0, 0}};
        matrixProblem(array, 0, 0);
        System.out.println("total possible solutions: ");
        System.out.println(possibility);
    }    

    static void matrixProblem(int[][] array, int i, int j) {
        if (i == r - 1 && j == c - 1) {
            possibility++;
            return;
        }

        if(i+1 < r) {
            if(array[++i][j] == 0) {
                matrixProblem(array, i, j);
            }
        }

        if(j+1 < c) {
            if(array[i][++j] == 0) {  
                matrixProblem(array, i, j);
            }
        }
    }
}

根据我的逻辑，它给出了错误的答案。

Answer 1

你的逻辑几乎是正确的，但问题出在递归调用时你传递递增的 i 值而不是传递 i+1. j 值相同。

编辑 1：

 if(i+1 < r) {
        if(array[i+1][j] == 0) {
                matrixProblem(array, i+1, j);
            }
        }

        if(j+1 < c) {
            if(array[i][j+1] == 0) {  
                matrixProblem(array, i, j+1);
            }
        }
}

使用递归解决矩阵问题时得到错误答案

getting wrong answer while soving matrix problem using recursion

matrix

data-structures