algorithm - 扫雷器的递归算法未按预期工作

Question

我试图理解递归，因此试图为扫雷游戏编写递归函数。我的程序没有游戏界面，只是为了理解。

这是我的理解:

我有一个给定大小的网格，其中将填充数字。为简单起见，我假设 0 代表我的，网格中的空单元格将由数字 9 表示。这是我的网格:
0 1 9 9 9
1 1 9 9 9
9 9 9 9 9
9 9 9 1 1
9 9 9 1 0

这是我的递归算法。我想我已经设置了正确的边界条件，但看起来像是进入无限递归的算法:

基本情况:
如果网格坐标小于 0 即 x<0 或 y<0 或 x> grid.length-1 或 y > grid.length-1
返回
其他
如果网格显示的数字不是 0 或 9 ，则显示数字即 grid[x][y]!=0 && grid[x][y]!=9
else 如果grid显示0表示是地雷，则显示Game over
否则
所有周围 8 个单元格的递归情况，因为所有周围单元格都可以安全打开

这里是一些代码来显示我在算法中列出的内容:

public static void playGame(int[][]grid, int x, int y){
        if(x > grid.length-1 || x <0 || y > grid.length-1 || y<0){
            return;
        }else{
            if(grid[x][y] !=0 && grid[x][y]!=9){
                //means this is a valid number to display to user
                System.out.println("opening cell:"+x+","+y+" "+grid[x][y]);
            }else if(grid[x][y] == 0){
                System.out.println("Game over!");
                //might want to show all mine locations
            }else{
                //all 8 cells are safe to open 
                playGame(grid,x-1,y-1); //left
                playGame(grid,x,y-1); //up
                playGame(grid,x,y+1);//down
                playGame(grid,x+1,y);//diagonal
                playGame(grid,x-1,y); //diagonal
                playGame(grid,x+1,y-1);//diagonal
                playGame(grid,x+1,y+1);//right
                playGame(grid,x-1,y+1);//diagonal

            }
        }
    }

我将单元格作为 2,2 传递，它给了我 java.lang.StackOverflowError。有人可以在这里指导我吗？我对算法或递归的理解是否有问题，或者我可能引入了一些错误。我无法发现问题。

Answer 1

在一般性建议之后，逐步检查在调试器中未按预期工作的代码，以解决给定的特定问题始终是个好主意。

您实现的问题似乎是打开空白字段，您没有跟踪已经访问过的字段。导致在相同的两个字段之间振荡的递归越来越深的问题。

根据您的示例中的数据，我用叉号 x 标记了实际访问的字段，并在顶部标记了调用堆栈，以向您展示我在说什么。

让我们从您的示例中给出的单元格 2、2 开始:

playGame(grid, 2, 2)
0 1 9 9 9
1 1 9 9 9
9 9 x 9 9
9 9 9 1 1
9 9 9 1 0

代码最终会调用 玩游戏(网格，x，y-1)；//向上

playGame(grid, 2, 2)
  playGame(grid, 2, 1)
0 1 9 9 9
1 1 x 9 9
9 9 9 9 9
9 9 9 1 1
9 9 9 1 0

我们将再次到达playGame(grid,x,y-1);//向上

playGame(grid, 2, 2)
  playGame(grid, 2, 1)
    playGame(grid, 2, 0)
0 1 x 9 9
1 1 9 9 9
9 9 9 9 9
9 9 9 1 1
9 9 9 1 0

由于这个字段仍然是空的，我们再次调用 playGame(grid,x,y-1);//向上

playGame(grid, 2, 2)
  playGame(grid, 2, 1)
    playGame(grid, 2, 0)
      playGame(grid, 2, -1)

这次我们将返回并 playGame(grid,x,y+1);//down 将被调用。

playGame(grid, 2, 2)
  playGame(grid, 2, 1)
    playGame(grid, 2, 0)
     playGame(grid, 2, 1)
0 1 9 9 9
1 1 x 9 9
9 9 9 9 9
9 9 9 1 1
9 9 9 1 0

由于此字段为空调用 playGame(grid,x,y-1);//up 将是下一步

playGame(grid, 2, 2)
  playGame(grid, 2, 1)
    playGame(grid, 2, 0)
      playGame(grid, 2, 1)
        playGame(grid, 2, 0)
0 1 x 9 9
1 1 9 9 9
9 9 9 9 9
9 9 9 1 1
9 9 9 1 0

从现在开始，我们将重复已经观察到的步骤，直到用完所有堆栈空间:

playGame(grid, 2, 2)
  playGame(grid, 2, 1)
    playGame(grid, 2, 0)
      playGame(grid, 2, 1)
        playGame(grid, 2, 0)
          playGame(grid, 2, 1)
            playGame(grid, 2, 0)
               ...