问题：

检查矩阵内的和并递归地保持第二个数组上的路径

弘浩瀚

2023-03-14

这个问题是在我Java期末考试中提出的：

给定一个正数矩阵(未排序)< code>m，一个整数< code>sum和另一个矩阵< code>p，该矩阵全部用< code>0填充。递归检查< code>m内部是否有一个路径，它的和等于< code>sum。

规则：

您只能在数组中向下、向上、向左或向右移动。

找到路径后，矩阵< code>p将用正确路径上的< code > 1 填充。

只有一条路径

方法完成后，p 上的所有其他单元格应为 0。

如果没有获得这笔金额的途径，您将保持< code>p的原样。

例：

        int[][] p = {{0,0,0,0},
                     {0,0,0,0},
                     {0,0,0,0},
                     {0,0,0,0}};

在一开始。

矩阵为：

        int [][] hill = {{3,8,7,1},
                         {5,15,2,4},
                         {12,14,-13,22},
                         {13,16,17,52}};

如果在 sum = 23 时调用该方法，则该方法将返回 true，并且 p 将为：

        int[][] p = {{1,0,0,0},
                     {1,1,0,0},
                     {0,0,0,0},
                     {0,0,0,0}};

该方法必须是递归的

这个问题让考试变得很糟糕。。。

希望你能弄明白，也许能帮助我理解！！谢谢

我的进度:

    public static boolean findSum(int[][] mat , int sum , int[][]path){
    return findSum(mat,sum,path,0,0);
}

private static boolean findSum(int[][] m, int sum, int[][] p, int i, int j) {
    if (i>=m.length || j>= m[i].length) return false;


    boolean op1 = finder(m,sum-m[i][j],p,i,j);
    boolean op2 = findSum(m,sum,p,i+1,j);
    boolean op3 = findSum(m,sum,p,i,j+1);

    if (op1) return true;
    else if (op2) return true;
    return op3;
}

private static boolean finder(int[][] m, int sum,int[][]p , int i, int j) {

    if (sum==0) {
        p[i][j]=1;
        return true;
    }
    p[i][j]=1;
    boolean op1=false,op2=false,op3=false,op4=false;
    if (i>0 && p[i-1][j]==0 && sum-m[i][j]>=0) op1 = finder(m, sum - m[i][j], p, i - 1, j);
    if (i<m.length-1 && p[i+1][j]==0&& sum-m[i][j]>=0) op2 = finder(m, sum - m[i][j], p, i + 1, j);
    if (j>0 && p[i][j-1]==0&& sum-m[i][j]>=0) op3 = finder(m, sum - m[i][j], p, i, j - 1);
    if (j<m[i].length-1 && p[i][j+1]==0&& sum-m[i][j]>=0) op4 = finder(m, sum - m[i][j], p, i, j + 1);
    else p[i][j]=0;
    return op1||op2||op3||op4;

}

共有2个答案

喻选

2023-03-14

所以我设法让它工作:)在我的课程讲师的帮助下，这是一个完整的java解决方案！

public static boolean findSum(int[][] m ,int s, int[][]p){
    return findSum(m,s,p,0,0); //calling overloading
}

private static boolean findSum(int[][] m, int s, int[][] p, int i, int j) {
    if (i<0 || i>=m.length) return false; //stop condition
    if (finder(m,s,p,i,j)) return true; //first recursion
    if (j<m[0].length-1) //if the iterator is not on the end of the row 
        return  findSum(m,s,p,i,j+1); //recursive call 
    else //if i checked the whole row , the column will be increase.
        return findSum(m,s,p,i+1,0);//recursive call

}

private static boolean finder(int[][] m, int s, int[][] p, int i, int j) {
    if (s == 0) return true;
    if (i<0 || i>=m.length || j<0 || j>=m.length || s<0 || p[i][j] == 1) return false;

    p[i][j] =1;
    boolean u=false,d=false,r=false,l=false;
    if (i>0) u = finder(m,s-m[i][j],p,i-1,j);
    if (i<m.length-1) d = finder(m,s-m[i][j],p,i+1,j);
    if (j>0) l = finder(m,s-m[i][j],p,i,j-1);
    if (i<m.length-1) r = finder(m,s-m[i][j],p,i,j+1);
    if (u) return true;
    else if (d) return true;
    else if (r) return true;
    else if (l) return true;
    else {
        p[i][j] = 0;
        return false;
    }
}

葛飞扬

2023-03-14

我真的很喜欢解决这个问题。我已经用python完成了它，但你可以很容易地将其扩展到Java。我已对代码进行了注释，以便您理解。如果您没有得到或可以改进的地方，请告诉我。

顺便说一句，在您的示例中，一个总和有多个路径，下面的代码可以找到所有路径。

hill = [[3,8,7,1],[5,15,2,4],[12,14,-13,22],[13,16,17,52]]
p = [ [0 for x in range (4)] for y in range(4)]
num = 23

def checkPath(p, r, c): #Check boundaries
    res = []
    if r+1<len(p):
        res.append(p[r+1][c] == 0)
    if r-1>=0:
        res.append(p[r-1][c] == 0)
    if c+1<len(p[0]):
        res.append(p[r][c+1] == 0)
    if c-1>=0:
        res.append(p[r][c-1] == 0)
    return res


def pathF(tot, hill, p, r, c):
    p[r][c] = 1 #mark visited
    tot = tot + hill[r][c]    #update total

    if tot == num: #solution found
        print("Found", p)
    else:
        if any (checkPath(p,r,c)):
            if r+1<len(p) and p[r+1][c] == 0: #move right checking if it wasnt visited
                  pathF(tot,hill,p,r+1,c)
            if r-1>=0 and p[r-1][c] == 0:
                pathF(tot,hill,p,r-1,c)
            if c+1<len(p[0]) and p[r][c+1] == 0:
                pathF(tot,hill,p,r,c+1)
            if c-1>=0 and p[r][c-1] == 0:
                pathF(tot,hill,p,r,c-1)
    p[r][c]=0 #mark unvisited
    tot = tot - hill[r][c]     #set total to original       


for x in range(len(hill)): #iterate over every starting point possible
    for y in range(len(hill[0])):
        pathF(0,hill,p,x,y)

这是num=23的输出

Found [[1, 0, 0, 0], [1, 0, 1, 0], [1, 1, 1, 0], [0, 0, 0, 0]]
Found [[1, 0, 0, 0], [1, 1, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]
Found [[1, 1, 1, 1], [0, 0, 0, 1], [0, 0, 0, 0], [0, 0, 0, 0]]
Found [[0, 1, 0, 0], [0, 1, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]
Found [[0, 1, 1, 1], [0, 0, 1, 1], [0, 1, 1, 0], [0, 0, 0, 0]]
Found [[0, 0, 1, 1], [0, 0, 1, 1], [0, 0, 1, 1], [0, 0, 0, 0]]
Found [[0, 0, 1, 1], [0, 0, 1, 1], [0, 0, 1, 1], [0, 0, 0, 0]]
Found [[0, 0, 1, 1], [0, 0, 1, 1], [0, 0, 1, 1], [0, 0, 0, 0]]
Found [[1, 1, 1, 0], [1, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]
Found [[0, 0, 1, 1], [0, 0, 1, 1], [0, 0, 1, 1], [0, 0, 0, 0]]
Found [[0, 0, 0, 1], [0, 1, 1, 1], [0, 1, 1, 0], [0, 0, 0, 0]]
Found [[0, 0, 0, 1], [0, 1, 1, 1], [0, 1, 1, 0], [0, 0, 0, 0]]
Found [[0, 0, 1, 1], [0, 0, 1, 1], [0, 0, 1, 1], [0, 0, 0, 0]]
Found [[0, 0, 1, 1], [0, 0, 1, 0], [1, 1, 1, 0], [0, 0, 0, 0]]
Found [[0, 0, 1, 1], [0, 0, 1, 1], [0, 0, 1, 1], [0, 0, 0, 0]]
Found [[1, 1, 1, 0], [1, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]
Found [[0, 0, 0, 0], [1, 1, 1, 0], [0, 1, 1, 0], [0, 0, 0, 0]]
Found [[0, 0, 0, 0], [1, 1, 1, 0], [0, 1, 1, 0], [0, 0, 0, 0]]
Found [[0, 0, 0, 1], [0, 1, 1, 1], [0, 1, 1, 0], [0, 0, 0, 0]]
Found [[0, 1, 0, 0], [0, 1, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]
Found [[1, 0, 0, 0], [1, 1, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]
Found [[0, 0, 1, 1], [0, 0, 1, 1], [0, 0, 1, 1], [0, 0, 0, 0]]
Found [[0, 0, 0, 0], [1, 1, 1, 0], [0, 1, 1, 0], [0, 0, 0, 0]]
Found [[1, 0, 0, 0], [1, 0, 1, 0], [1, 1, 1, 0], [0, 0, 0, 0]]
Found [[0, 0, 1, 1], [0, 0, 1, 1], [0, 0, 1, 1], [0, 0, 0, 0]]
Found [[0, 0, 1, 1], [0, 0, 1, 1], [0, 0, 1, 1], [0, 0, 0, 0]]
Found [[0, 0, 1, 1], [0, 0, 1, 1], [0, 0, 1, 1], [0, 0, 0, 0]]
Found [[1, 1, 1, 1], [0, 0, 0, 1], [0, 0, 0, 0], [0, 0, 0, 0]]
Found [[0, 0, 0, 0], [0, 0, 1, 1], [0, 1, 1, 0], [0, 1, 0, 0]]
Found [[0, 0, 1, 1], [0, 0, 1, 0], [1, 1, 1, 0], [0, 0, 0, 0]]
Found [[0, 1, 1, 1], [0, 0, 1, 1], [0, 1, 1, 0], [0, 0, 0, 0]]
Found [[0, 0, 0, 0], [1, 1, 1, 0], [0, 1, 1, 0], [0, 0, 0, 0]]
Found [[0, 0, 0, 0], [0, 0, 0, 0], [0, 1, 1, 1], [0, 0, 0, 0]]
Found [[0, 0, 1, 1], [0, 0, 1, 1], [0, 0, 1, 1], [0, 0, 0, 0]]
Found [[0, 0, 1, 1], [0, 0, 1, 1], [0, 0, 1, 1], [0, 0, 0, 0]]
Found [[0, 0, 1, 1], [0, 0, 1, 1], [0, 0, 1, 1], [0, 0, 0, 0]]
Found [[0, 0, 0, 1], [0, 1, 1, 1], [0, 1, 1, 0], [0, 0, 0, 0]]
Found [[0, 0, 1, 1], [0, 0, 1, 1], [0, 0, 1, 1], [0, 0, 0, 0]]
Found [[0, 0, 1, 1], [0, 0, 1, 1], [0, 0, 1, 1], [0, 0, 0, 0]]
Found [[0, 0, 1, 1], [0, 0, 1, 1], [0, 0, 1, 1], [0, 0, 0, 0]]
Found [[0, 0, 0, 0], [0, 0, 0, 0], [0, 1, 1, 1], [0, 0, 0, 0]]
Found [[0, 0, 0, 0], [0, 0, 1, 1], [0, 1, 1, 0], [0, 1, 0, 0]]

类似资料：

递归路径查找0,1矩阵（并保存所有可能的路径）java

我正在尝试编写一个递归方法，它可以找到一个路径，而不需要回溯到一个int矩阵中的一个位置，这个矩阵包含值0，1。0可以踩，1不行。我也限制了一条超过50步的路径。 Location是一个具有行和列值(x，y)的对象。locationEquals是一个函数，如果两个位置相同，则返回true，否则返回false。map变量是我试图在其中找到路径的矩阵。执行以下代码后'选项'为空，这意味着它没有找到方
检查数组的递归

在PHP中，检查数组是否为递归数组的最佳方法是什么？给定以下代码：从PHP手册： print\u r（）在到达数组的第三个元素时将显示递归。似乎没有其他方法可以扫描数组中的递归引用，因此如果需要检查它们，则必须使用print\u r（）及其第二个参数来捕获输出并查找单词RECURSION。还有更优雅的检查方式吗？附：这就是我如何使用regex和print\u r（）检查和获取递归数组键的
递归查找并行数组上的值

我需要编写一个递归方法，它需要两个并行数组和单词来查找，查找指定的单词并在另一个数组上每次索引匹配时求和值。例如：如果我说我需要查找单词，它应该在找到索引时对第二个数组上的值求和。在这种情况下，它应该求和，。如何使我的递归方法使其采用适当的参数并递归地进行计算。我将使用硬编码值。这是我目前所拥有的。我很确定我的递归方法需要更多参数，但我会看看是否有人能帮助我
在矩阵中查找区域的递归函数

给定一个矩阵（包含布尔值-true/false）。我们将定义：数组中的真实区域，作为所有具有真实值的相邻单元格的最大集合。相互对角定位的单元格不被认为是相邻的。在本例中，有3个真实区域：真实区域我的解决方案在Java中尝试：这显然不起作用。我在考虑遍历每个单元格，如果该单元格有真值，则在总区域（不知何故）中加1，然后将该值设为假，并将该值设为假（将该区域标记为“已访问”）。虽然我发现
第二章数组 - 2.8 矩阵相乘

题目描述请编程实现矩阵乘法，并考虑当矩阵规模较大时的优化方法。分析与解法根据wikipedia上的介绍：两个矩阵的乘法仅当第一个矩阵A的行数和另一个矩阵B的列数相等时才能定义。如A是m×n矩阵，B是n×p矩阵，它们的乘积AB是一个m×p矩阵，它的一个元素其中 1 ≤ i ≤ m, 1 ≤ j ≤ p。值得一提的是，矩阵乘法满足结合律和分配率，但并不满足交换律，如下图所示的这个例子，两个矩阵
关于矩阵和数组的其他内容

这一节将给你展现更多关于矩阵和数组的内容。集中在以下内容: 线性代数数组多元数据

检查矩阵内的和并递归地保持第二个数组上的路径

共有2个答案

相关问答

相关文章

相关阅读

相关工具

相关文档