java-给定2d整数数组,递归找到总和为给定数字的路径

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了java-给定2d整数数组,递归找到总和为给定数字的路径，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2247字，纯文字阅读大概需要4分钟。

内容图文

给定一个二维数组,我需要递归地返回一个矩阵,该矩阵的路径总和为给定的数字.

路径矩阵应为零,但路径的总和等于给定数字,该数字将标记为1.

路径只能在

我已经尝试过所有可能性,首先检查是否已经到下一个区块.

问题是经过一些迭代后,它停止了,并且没有返回并再次将该块清除为0.

private static boolean paintPath(int[][] mat, int sum, int[][] path , int i, int j){

        if(sum<0)
            return false;

        path[i][j] = 1;

        if(sum == 0)
            return true;
        printMat(path);
        System.out.println();

        if(withinBoundaries(mat,i+1,j) && path[i+1][j] != 1)
            if(paintPath(mat,sum - mat[i][j],path,i+1,j))
                return true;

        if(withinBoundaries(mat,i,j+1) && path[i][j+1] != 1)
            if(paintPath(mat,sum - mat[i][j],path,i,j+1))
                return true;

        if(withinBoundaries(mat,i-1,j) && path[i-1][j] != 1)
            if(paintPath(mat,sum - mat[i][j],path,i-1,j))
                return true;
        if(withinBoundaries(mat,i,j-1) && path[i][j-1] != 1)
            if(paintPath(mat,sum - mat[i][j],path,i,j-1))
                 return true;

        path[i][j] = 0;
        return false;

    }

给定

int[][] mat1 = {
                {1,1,1,1},
                {5,100,100,1},
                {100,100,100,1},
                {1,1,1,1}
        };


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

与电话

paintPath(mat1, 5, path, 0, 0);

我希望算法能够返回

        {0,0,0,0},
        {1,0,0,0},
        {0,0,0,0},
        {0,0,0,0}

我懂了

1   1   1   1   
0   0   1   1   
0   0   0   0   
0   0   0   0

代替.

然后从对paintPath(mat1,400,path,0,0)的调用中；
我预计

        {0,0,0,0},
        {0,1,1,0},
        {0,1,1,0},
        {0,0,0,0}

要么

        {0,0,0,0},
        {0,0,1,0},
        {1,1,1,0},
        {0,0,0,0}

问题是我的算法从(0,0)开始并从那里寻找路径,我需要它从任何起点找到任何路径(无循环)

编辑：
作业中引用的问题：
“我们将数组中的路径定义为相邻单元格的集合.
相邻的cekk可以从左,右,上,下相邻,但不能是对角线.
每个单元只能在路径中累积一次.
编写一个递归方法,该方法接受一个2d数组mat,该数组包含大于0的整数,一个整数和正数以及一个与mat大小相同的2d数组路径.

要求该方法检查数组中是否存在其值之和等于sum的路径.
如果存在这样的路径,则应返回true,false otherwize.

数组路径用于标记总和等于总和的路径.

path在路径单元格中的位置为1,在其他单元格中的位置为0.

该方法必须是递归的,完全没有循环！
就像您将要编写的任何其他方法一样.

您可以使用重载.

你不能换垫子.

解决方法:

改变这个

path[i][j] = 1;

if(sum == 0)
  return true;
printMat(path);
System.out.println();

对此：

if(sum == 0){
  printMat(path);
  System.out.println();
  return true;
}

path[i][j] = 1;

请注意,您将获得输出,

{0,0,0,0},
{1,0,0,0},
{0,0,0,0},
{0,0,0,0}

如果您将开始通话更改为

paintPath(mat1, 5, path, 1, 0);

内容总结

以上是互联网集市为您收集整理的java-给定2d整数数组,递归找到总和为给定数字的路径全部内容，希望文章能够帮你解决java-给定2d整数数组,递归找到总和为给定数字的路径所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端