java - 使用递归在二维数组中查找 4 个连续的 1

Question

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

如果上面是我的输入，我的代码应该在其中找到四个连续的 1。我知道我们必须使用环绕数组来解决这个问题，但我不知道如何实现它。这是修改后的代码

public static boolean findFourOnes(int[][] arr){
    for(int i = 0; i < arr.length; i++){
        if(findVertical(arr, i, 0, 0)){
            return true;
        }
    }
    for(int i = 0; i < arr.length; i++){
        if(findHorizontal(arr, 0, i, 0)){
            return true;
        }
    }
    return false;
}
public static boolean findVertical(int[][] arr, int x, int y, int counter){
    //base case
    if(counter == 4)
        return true;

    if(arr[x][y] == 1)//consecutive 
        counter++;
    else//not consecutive
        counter = 0;

   y++;

    // wrap around case
    if(y == arr.length - 1|| y == arr.length +1){
        int max_size=4;
        if(y < 0) {y=x + max_size; return findVertical(arr, x, y, counter);}
        else if(y >= max_size) {y=x % max_size;return findVertical(arr, x, y, counter);}


    }

    return false;
}
public static boolean findHorizontal(int[][] arr, int x, int y, int counter){
    //base case
    if(counter == 4)
        return true;

    if(arr[x][y] == 1)//consecutive 
        counter++;
    else//not consecutive
        counter = 0;

   x++;

    // wrap around case
    if(x == arr.length - 1|| x == arr.length +1){
        int max_size=4;
        if(x < 0) {x=x + max_size;    return findHorizontal(arr, x, y, counter);}
        else if(x >= max_size) {x=x % max_size;    return findHorizontal(arr, x, y, counter);}

    }

   return false;


}

此代码仅检查数组中是否有四个连续的 1。如果它正常工作，我的矩阵是 4X4。在此代码中，我的数组 b 为空且为零。如果我找到四个 1，我将更新该矩阵。

Answer 1

Cyber​​neticTwerkGuruOrc 解决方案的纯递归变体:

public class FourOnes {

    public static boolean solveArrayRecursively(int[][] array) {
        return solveRowsRecursively(array, 0, 0, 0) || solveColumnsRecursively(array, 0, 0, 0);
    }

    public static boolean solveColumnsRecursively(int[][] array, int x, int y, int found) {
        if(found >= 4) {
            // We have 4 consecutive ones
            return true;
        }
        if(x != 0 && x >= array.length) {
            // next column
            return solveColumnsRecursively(array, 0, y + 1, 0);
        }
        if(x >= array.length || y >= array[x].length) {
            // no more columns
            return false;
        }
        if(array[x][y] == 1) {
            // found another 1
            return solveColumnsRecursively(array, x + 1, y, found + 1);
        } else {
            // reset count to 0 as there is a gap in the sequence
            return solveColumnsRecursively(array, x + 1, y, 0);
        }
    }

    public static boolean solveRowsRecursively(int[][] array, int x, int y, int found) {
        if(found >= 4) {
            // We have 4 consecutive ones
            return true;
        }
        if(x >= array.length ) {
            // no more rows
            return false;
        }
        if(y >= array[x].length) {
            // next row
            return solveRowsRecursively(array, x + 1, 0, 0);
        }
        if(array[x][y] == 1) {
            // found another 1
            return solveRowsRecursively(array, x, y + 1, found + 1);
        } else {
            // reset count to 0 as there is a gap in the sequence
            return solveRowsRecursively(array, x, y + 1, 0);
        }
    }

    public static void main(String[] args) {
        System.out.println(solveArrayRecursively(new int[][] {
                new int[] {1, 1, 0, 0},
                new int[] {0, 0, 0, 0},
                new int[] {0, 0, 0, 0},
                new int[] {0, 0, 1, 1}
        }));
        System.out.println(solveArrayRecursively(new int[][] {
                new int[] {1, 1, 0, 0},
                new int[] {0, 0, 0, 0},
                new int[] {1, 1, 1, 1},
                new int[] {0, 0, 1, 1}
        }));
        System.out.println(solveArrayRecursively(new int[][] {
                new int[] {1, 1, 1, 0},
                new int[] {0, 0, 1, 0},
                new int[] {0, 0, 1, 0},
                new int[] {0, 0, 1, 1}
        }));
        System.out.println(solveArrayRecursively(new int[][] {
                new int[] {1, 1, 1, 1},
                new int[] {1, 1, 1, 1},
                new int[] {1, 1, 1, 1},
                new int[] {1, 1, 1, 1}
        }));
        System.out.println(solveArrayRecursively(new int[0][0]));
    }
}

备用:

    public static boolean solveArrayRecursively(int[][] array) {
        return solveRecursively(array, 0, 0, 0, 0);
    }

    public static boolean solveRecursively(int[][] array, int x, int y, int foundX, int foundY) {
        if(foundX >= 4 || foundY >= 4) {
            return true;
        }
        if(x >= array.length || y >= array[x].length) {
            return false;
        }
        if(array[x][y] == 1) {
            return solveRecursively(array, x + 1, y, foundX + 1, 1)
                    || solveRecursively(array, x, y + 1, 1, foundY + 1);
        } else {
            return solveRecursively(array, x + 1, y, 0, 0)
                    || solveRecursively(array, x, y + 1, 0, 0);
        }
    }

请注意，虽然在某些情况下交替执行会更好，但它不是简单的[尾递归](http://en.wikipedia.org/wiki/Tail_call]，它会增加堆栈溢出的风险数组，而第一个解决方案将在调试中产生更多的堆栈溢出，因为尾递归很可能没有优化。

另请注意，第一个解决方案采用 1 + 2*(columns+1)*(rows+1) 调用，最大递归深度为 1 + (columns+1) *(rows+1) 其中第二个调用的最大深度为 1 + 列 + 行，如下所示:

   x=0 x=1 x=2 x=3 x=4y=0 1   1   1   1   1y=1 1   2   3   4   4y=2 1   3   6   10  10y=3 1   4   10  20  20y=4 1   4   10  20