java - 如何以非破坏性方式防止无限递归？

Question

这是我的第一个问题，所以如果我没有足够好地挖掘数据并重复这个问题，我提前道歉。

所以我正在尝试创建某种游戏，在某些时候你有一个像这样的矩阵:

 _ _ _ _ _ _
|_|_|h|h|h|h|
|_|_|_|_|_|_|
|_|#|#|#|_|_|
|_|_|_|#|_|_|
|_|h|_|_|_|_|
|_|h|#|_|_|_|   

我需要一种方法来检查是否存在仅由“h”-es 组成的“元素”，如果找到一个，则将所有字符从“h”更改为其他字符，例如“d”，这样它变成:

 _ _ _ _ _ _
|_|_|d|d|d|d|
|_|_|_|_|_|_|
|_|#|#|#|_|_|
|_|_|_|#|_|_|
|_|h|_|_|_|_|
|_|h|#|_|_|_|   

虽然它不应该改变其他的 'h'-es，但触摸 '#'-s我可以使用 for-cycles 遍历整个矩阵，或者直接从元素开始，因为我有 arr[y][x] 坐标。无论哪种方式，我都在使用递归来检查邻居，但是如何防止该方法返回到前一个元素并在它们之间振荡直到... StackOverflow 发生？到目前为止，这就是我所在的位置:

public class matrixRec {
    public static void main(String[] args) {
        char[][] matrix = {
            {' ',' ',' ',' ',' ',' '},
            {' ','h','h','h','h',' '},
            {' ',' ',' ',' ',' ',' '},
            {' ',' ',' ','#','#',' '},
            {' ','h',' ',' ','#','#'},
            {' ','h','#',' ',' ',' '}
        };
        System.out.println(elementChange(matrix, 1, 2));
    }
    static boolean elementChange(char[][] matrix, int y, int x){

        if (matrix[y][x] == ' '){
            return true;
        }
        else if (matrix[y][x] == '#'){
            return false;
        }
        else if (matrix[y][x] == 'h'){
            return (elementChange(matrix, y, x-1) && elementChange(matrix, y, x+1));
        }
        else {
            return false;
        }
    }
}

那么有没有一种方法可以防止无限递归，而无需更改“h”-es，直到我确定它们都是“h”？

Answer 1

要做的几件事:

每次我们检查一个区域时创建一个 boolean 数组来检查访问过的单元格

public class matrixRec {
    public static void main(String[] args) {
        char[][] matrix = {
            {' ',' ',' ',' ',' ',' '},
            {' ','h','h','h','h',' '},
            {' ',' ',' ',' ',' ',' '},
            {' ',' ',' ','#','#',' '},
            {' ','h',' ',' ','#','#'},
            {' ','h','#',' ',' ',' '}
        };
        boolean visited[][] = new boolean[6][6] //boolean arrays default to false
        System.out.println(elementChange(matrix, 1, 2, visited));
    }
    static boolean elementChange(char[][] matrix, int y, int x. boolean[][] visited){
        if(visited[y][x]) return ((matrix[y][x] == ' ' || matrix[y][x] == 'h')? true: false);
        visited[y][x] = true; //We have visited this cell
        if (matrix[y][x] == ' '){
            return true;
        }
        else if (matrix[y][x] == '#'){
            return false;
        }
        else if (matrix[y][x] == 'h'){
            return elementChange(matrix, y, x-1,visited) && elementChange(matrix, y, x+1,visited);
        }
        else {
            return false;
        }
    }
}

我们只是检查左右吗？上下呢？

public class matrixRec {
    public static void main(String[] args) {
        char[][] matrix = {
            {' ',' ',' ',' ',' ',' '},
            {' ','h','h','h','h',' '},
            {' ',' ',' ',' ',' ',' '},
            {' ',' ',' ','#','#',' '},
            {' ','h',' ',' ','#','#'},
            {' ','h','#',' ',' ',' '}
        };
        boolean visited[][] = new boolean[6][6] //boolean arrays default to false
        System.out.println(elementChange(matrix, 1, 2, visited));
    }
    static boolean elementChange(char[][] matrix, int y, int x. boolean[][] visited){
        if(visited[y][x]) return ((matrix[y][x] == ' ' || matrix[y][x] == 'h')? true: false);
        visited[y][x] = true; //We have visited this cell
        if (matrix[y][x] == ' '){
            return true;
        }
        else if (matrix[y][x] == '#'){
            return false;
        }
        else if (matrix[y][x] == 'h'){
            return elementChange(matrix, y, x-1,visited) && elementChange(matrix, y, x+1,visited) && elementChange(matrix, y-1, x,visited) && elementChange(matrix, y+1, x,visited);
        }
        else {
            return false;
        }
    }
}

使用条件语句仅更改我们想要更改的区域

public class matrixRec {
    public static void main(String[] args) {
        char[][] matrix = {
            {' ',' ',' ',' ',' ',' '},
            {' ','h','h','h','h',' '},
            {' ',' ',' ',' ',' ',' '},
            {' ',' ',' ','#','#',' '},
            {' ','h',' ',' ','#','#'},
            {' ','h','#',' ',' ',' '}
        };
        boolean visited[][] = new boolean[6][6] //boolean arrays default to false
        System.out.println(elementChange(matrix, 1, 2, visited));
    }
    static boolean elementChange(char[][] matrix, int y, int x. boolean[][] visited){
        if(visited[y][x]) return ((matrix[y][x] == ' ' || matrix[y][x] == 'h')? true: false);
        visited[y][x] = true; //We have visited this cell
        if (matrix[y][x] == ' '){
            return true;
        }
        else if (matrix[y][x] == '#'){
            return false;
        }
        else if (matrix[y][x] == 'h'){

            if((elementChange(matrix, y, x-1,visited) && elementChange(matrix, y, x+1,visited) && elementChange(matrix, y-1, x,visited) && elementChange(matrix, y+1, x,visited))
                matrix[y][x] = 'd'; //Will only change areas that were searched to not be next to a #
        }
        else {
            return false;
        }
    }
}

为了 future

这是一个需要一点思考和规划的算法领域。对于 future 的研究/计划，一定要对洪水填充、递归回溯、图形搜索和递归迷宫求解进行一些搜索。