Minesweeper的递归算法未按预期工作

debugcn 发表于 Dev

希娜（Shyna）

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

这是我的理解：

我有给定大小的网格，其中将填充数字。为简单起见，我假设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 OR x> grid.length-1或y> grid.length-1
返回
ELSE
如果网格显示的数字不是0或9，则显示数字，即grid [x] [y]！= 0 && grid [x] [y]！= 9
否则，如果grid显示0表示它是我的地雷，则对所有周围的8个像元的所有周围的递归案例显示Game over
else
牢房可以安全打开

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

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。有人可以在这里指导我吗？我对算法或递归的理解是否有问题，或者我可能已经引入了一些错误。我无法发现问题。

米基拉

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

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

给定您示例中的数据，我用一个叉号标记了实际访问的字段，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

代码将最终调用 playGame(grid,x,y-1); //up

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); //up

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); //up

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)
               ...

本文收集自互联网，转载请注明来源。

如有侵权，请联系[email protected] 删除。

编辑于2021-06-11

我来说两句

0条评论

登录后参与评论

来自分类Dev

Related 相关文章

文章