扫雷递归算法搞不懂

Question

我无法弄清楚在扫雷中显示空单元格的算法。 revealCells 应该取一个单元格，然后检查周围的单元格并显示它们，直到找到地雷单元格，但由于某种原因，我一直收到 arrayindexoutofbounds 异常。 Cells 是板上单元格的二维数组。我知道我并没有检查所有条件，我只需要在添加其余条件之前测试它是否有效。

public void revealCells(Cell cell){
    row = cell.getRow();
    column = cell.getCol();

    if (row < 0 || row > cells.length - 1|| column < 0 || column > cells.length - 1) return;

    else if(cell instanceof MineCell) return;       

    else if(cell.getMineCount() == 0 && !(cell.isRevealed())){
        cell.reveal();
        revealCells(cells[row+1][column]);
        revealCells(cells[row][column+1]);
        revealCells(cells[row-1][column]);
        revealCells(cells[row][column-1]);
        revealCells(cells[row+1][column+1]);
        revealCells(cells[row-1][column-1]);
    }
    else{
        return;
    }
}

Answer 1

这并不奇怪：你做一个递归调用：

revealCells(cells[row+1][column]);

这意味着 Java 将首先获取

cells[row+1][column]

。现在你没有做任何边界检查。方法中的绑定检查可能没什么用，因为那时你已经得到了单元格，所以你知道它是一个有效的坐标。

在我看来，你最好重新设计你的系统以使用坐标而不是单元格，然后在边界检查后获取单元格：

public void revealCells(int row, int column) {
    if (row < 0 || row >= cells.length|| column < 0 || column >= cells[0].length)
        return;

    Cell cell = cells[row][column]; // now we are safe, so fetch the cell
    if(cell instanceof MineCell)
        return;   

    else if(cell.getMineCount() == 0 && !(cell.isRevealed())){
        cell.reveal();
        // call recursive with coordinates, not cells
        revealCells(row-1,column-1);
        revealCells(row-1,column);
        revealCells(row-1,column+1);
        revealCells(row,column-1);
        revealCells(row,column+1);
        revealCells(row+1,column-1);
        revealCells(row+1,column);
        revealCells(row+1,column+1);
    }
}

Answer 2

查看此视频“使用扫雷器学习递归算法”

https://www.youtube.com/watch?v=uH1tMf2CKPw

和演讲者的 GitHub 页面：

https://github.com/kubowania/minesweeper