在二维数组中查找 "path"，其中路径单元格总和等于 "sum"

Question

给定正整数的二维数组。 "path" 是相邻单元格的集合。两个单元格仅从 right/left/top/bottom（无对角线）相邻。

任务是编写一个函数，接收一个二维数组mat、一个整数sum和一个二维数组path（大小与mat-空数组全为零）。

该函数应检查单元格总和等于 sum 的路径是否存在，如果存在则应 return 为真，否则为假。

数组path将标记路径（如果存在1）。

例如，如果 mat 是：

和sum=4

那么path可以是这三个之一：

我的代码：

public static void main(String[] args) 
{
    int[][] mat={{2,41,3,14},
                 {2,1,24,7},
                 {2,15,10,54},
                 {63,22,2,4}};

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

public static boolean findSum (int mat[][], int sum, int path[][],int i,int j)
{
    if(sum==0)                      
        return true;

    if(i==mat[0].length||j==mat[1].length)
        return false;       
    boolean result=findSum(mat,sum-mat[i][j],path,i,j+1)||findSum(mat,sum-mat[i][j],path,i+1,j);

    if(result)
        path[i][j]=1;
    return result;

}
private static void print(int[][] arr)
{
    for(int i=0;i<arr[0].length;i++)
    {
        for(int j=0;j<arr[0].length;j++)
        {
            System.out.print(arr[i][j]+" ");
        }
        System.out.println();
    }
}

My code works fine only if the path starts at (0,0) but does't work for other pathes, for example it doesn't work(path array is all zero) for sum=16 even that there is such path.

注：

该函数必须是递归的 - 完全没有循环。
不允许使用全局变量（打印数组不是问题的一部分 - 仅用于测试，因此存在循环）

Answer 1

问得好...答案在这里。这是一个有趣的代码挑战 ;)

public static void main(String[] args) 
{
    int[][] mat={{2,41,3,14},
                 {2,1,24,7},
                 {2,15,10,54},
                 {63,22,2,4}};

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

    if ( findSum(mat,22,path) ) print(path);
    else System.out.println("No path found");
}
public static boolean findSum (int mat[][], int sum, int path[][])
{
    return startPath(mat, sum, path, -1, 0);
}

// Recursively check every possible starting point
public static boolean startPath(int mat[][], int sum, int path[][], int y, int x)
{
    // Iterate y, goto next column if necessary
    if (++y == mat.length) {
        y = 0;
        ++x;
    }

    if (x == mat[0].length) // Bounds check
        return false;

    if (findSum(mat, sum, path, y, x)) // We've found a successful start point!
    {
        System.out.println("A successful path starts at " + x + ", " + y);
        return true;
    }

    return startPath(mat, sum, path, y, x); // We'll have to keep looking
}

public static boolean findSum (int mat[][], int sum, int path[][], int i, int j)
{
    if(i==mat[0].length || j==mat[1].length || i<0 || j<0) // Bounds check
        return false;

    if (path[i][j] == 1) // Backtracking check
        return false;

    sum -= mat[i][j]; // Decrement sum

    if (sum >= 0) { // More to go? look around
        path[i][j] = 1;

        if (sum == 0) return true; // We made it!

         // If any path finds the end, don't try other paths
        boolean result = findSum(mat, sum, path, i+1, j);
        if (result) return true;
        result = findSum(mat, sum, path, i, j+1);
        if (result) return true;
        result = findSum(mat, sum, path, i-1, j);
        if (result) return true;
        result = findSum(mat, sum, path, i, j-1);

         // There was no successful paths, this is a dead end
        if (!result) path[i][j] = 0;
        return result;
    } else { // We're negative, overshot it
        return false;
    }
}

private static void print(int[][] arr)
{
    for(int i=0;i<arr[0].length;i++)
    {
        for(int j=0;j<arr[0].length;j++)
        {
            System.out.print(arr[i][j]+" ");
        }
        System.out.println();
    }
}

顺便说一句，在检查多维数组维度时，你打算做 arr.length and arr[0].length 但你做的是 arr[0].length and arr[1].length 如果数组不是广场.

我还允许向任何方向移动，方法是使用预期的路径来防止再次 re-checking 相同的节点。这可能是一个布尔数组。抱歉，如果我的 x/y 递归看起来很粗糙......我真的更喜欢循环或 .forEach 或 => 或 .map ......

也许可以使用可选参数清除 -1、0，而不是在第一次遍历时进行迭代。

如果您发现任何错误或极端情况，请告诉我。

在二维数组中查找 "path"，其中路径单元格总和等于 "sum"

Find "path" in 2D array where path cells sum equals to "sum"

java

recursion

backtracking