x*y的方格,从A点到B点,A点只能想下或者向右,求共有几条不重复路径,打印出路径

题目:

x*y的方格,从A点到B点,A点只能想下或者向右,求共有几条不重复路径,打印出路径

如图所示

x*y的方格,从A点到B点,A点只能想下或者向右,求共有几条不重复路径,打印出路径

 

其实这是数学排列组合中的题目数学公式如下
x*y的方格,从A点到B点,A点只能想下或者向右,求共有几条不重复路径,打印出路径

 

不适用公式计算的话,如何计算?

我用的是递归的方法代码如下:

    static int row = 100;
    static int line = 100;
    static Integer[][] source = new Integer[row][line];
    static int startI = 0;
    static int startJ = 0;
    static int endI = 4;
    static int endJ = 4;
    static int num = 0;
    static ArrayList<Integer> temp = new ArrayList<>();
    static ArrayList<String> route = new ArrayList<>();

    public static Integer[][] getSource() {

        int val = 0;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < line; j++) {
                source[i][j] = val;
                val++;
            }
        }
        return source;
    }

    public static void main(String[] args) {
        getSource();
        deal(startI, startJ);
        System.out.println(num);
        System.out.println(route);
    }

    public static void deal(int i, int j) {
        if( i <= endI && j <= endJ){
            temp.add(source[i][j]);
        }
        if (i == endI && j == endJ) {
            route.add(temp.toString());
            num++;
        }
        if (i > endI || j > endJ) {
            return;
        }
        deal(i + 1, j);
        if( i + 1 <= endI && j <= endJ){
            temp.remove(source[i + 1][j]);
        }
        deal(i, j + 1);
        if( i <= endI && j + 1 <= endJ){
            temp.remove(source[i][j + 1]);
        }
    }

 




 

上一篇:python xpath xml namespaces|How does XPath deal with XML namespaces?


下一篇:删除数据库中的指定数据