java - 递归扫雷“0-fill”

Question

我正在创建一个 Java 的 Java 实现来取乐，当您单击它们的池时，我试图填充所有零。（玩扫雷看看我在说什么）

这是我的递归调用：

private void revealZeros(int x, int y) {

    if (board[y][x].revealed)
        return;
    board[y][x].revealed = true;
    if (y > 0) {
        if (x > 0)
            if (!board[y - 1][x - 1].revealed && board[y - 1][x - 1].b == 0)
                revealZeros(y - 1, x - 1);
        if (x < 15) {
            if (!board[y - 1][x + 1].revealed && board[y - 1][x + 1].b == 0)
                revealZeros(y - 1, x + 1);
        }
        if (!board[y - 1][x].revealed && board[y - 1][x].b == 0)
            revealZeros(y - 1, x);
    }
    if (x > 0)
        if (!board[y][x - 1].revealed && board[y][x - 1].b == 0)
            revealZeros(y, x - 1);
    if (x < 15)
        if (!board[y][x + 1].revealed && board[y][x + 1].b == 0)
            revealZeros(y, x + 1);
    if (y < 15) {
        if (x > 0)
            if (!board[y + 1][x - 1].revealed && board[y + 1][x - 1].b == 0)
                revealZeros(y + 1, x - 1);
        if (x < 15)
            if (!board[y + 1][x + 1].revealed && board[y + 1][x + 1].b == 0)
                revealZeros(y + 1, x + 1);
        if (!board[y + 1][x].revealed && board[y + 1][x].b == 0)
            revealZeros(y + 1, x);
    }

}

呼叫无法正常工作。它显示除 0 以外的块，并且不显示所有 0 块。

Space.b = 它周围的炸弹数量
Space.revealed = 空间暴露了吗？

Answer 1

哇！！我能够想到一个解决方案。非常简单。这是我的结束代码：

private void revealZeros(int x, int y) {
        if (x < 0 || x > 15 || y < 0 || y > 15) return; // check for bounds

           if ( board[y][x].b == 0 && !board[y][x].revealed) {
               board[y][x].revealed = true;
               revealZeros( x+1, y );
               revealZeros( x-1, y );
               revealZeros( x, y-1 );
               revealZeros( x, y+1 );
           } else {
               return;
           }
        }

Answer 2

很抱歉直言不讳，但你的代码很疯狂。递归应该简化您的代码，使其更小更容易，但代价是更多的内存使用。例如，我的 MineSweeper 实现中的递归方法是：

  private void zeroValuePress(int row, int col) {
     int rMin = Math.max(row - 1, 0);
     int cMin = Math.max(col - 1, 0);
     int rMax = Math.min(row + 1, cellModelGrid.length - 1);
     int cMax = Math.min(col + 1, cellModelGrid[row].length - 1);
     for (int row2 = rMin; row2 <= rMax; row2++) {
        for (int col2 = cMin; col2 <= cMax; col2++) {
           cellModelGrid[row2][col2].pressedAction();
        }
     }
  }

它不直接调用自己，而是调用它周围所有单元格的 pressAction 方法，这会将它们的状态更改为pressed. PropertyChangeListeners 然后启动以返回此代码。MVC之美。

整个 PropertyChangeListener：

private class CellModelPropertyChangeListener implements
        PropertyChangeListener {

  public void propertyChange(PropertyChangeEvent evt) {
     MineCellModel model = (MineCellModel) evt.getSource();
     int row = model.getRow();
     int col = model.getCol();

     if (evt.getPropertyName().equals(MineCellModel.BUTTON_PRESSED)) {
        if (cellModelGrid[row][col].isMineBlown()) {
           mineBlown();
        } else {
           buttonsRemaining--;
           if (buttonsRemaining <= 0) {
              JOptionPane.showMessageDialog(null, "You've Won!!!", "Congratulations", JOptionPane.PLAIN_MESSAGE);
           }
           if (cellModelGrid[row][col].getValue() == 0) {
              zeroValuePress(row, col);
           }
        }
     }
  }

  private void mineBlown() {
     for (int r = 0; r < cellModelGrid.length; r++) {
        for (int c = 0; c < cellModelGrid[r].length; c++) {
           MineCellModel model = cellModelGrid[r][c];
           if (model.isMined()) {
              model.setMineBlown(true);
           }
        }
     }

  }

  private void zeroValuePress(int row, int col) {
     int rMin = Math.max(row - 1, 0);
     int cMin = Math.max(col - 1, 0);
     int rMax = Math.min(row + 1, cellModelGrid.length - 1);
     int cMax = Math.min(col + 1, cellModelGrid[row].length - 1);
     for (int row2 = rMin; row2 <= rMax; row2++) {
        for (int col2 = cMin; col2 <= cMax; col2++) {
           cellModelGrid[row2][col2].pressedAction();
        }
     }
  }
}

Answer 3

在我们大学的合作伙伴工作中，我们使用了以下递归方法。有 2 个 2D 数组，一个保存解决方案，另一个保存用户输出（控制台）的可见字段。

它还打开零字段旁边的任何数字字段（如 ms minesweeper 中）。它在 1000x1000 字段（stackoverflow）周围变得混乱 - 但无论如何这将是一场漫长的比赛......

private void openSurroundingFields(int i, int e) {
  for (int j=i-1;j<i+2;j++)              
     for (int h=e-1;h<e+2;h++)
         if ( (j>-1) && (j<field.length) && (h>-1) && (h<field[0].length) && (field[j][h] != ZERO_SYMBOL)){
            if (mineField[j][h] == 0){ 
              field[j][h] = ZERO_SYMBOL;
              openSurroundingFields(j, h);
            } 
            else if (mineField[j][h] != -1)
               field[j][h] = Integer.toString(mineField[j][h]).charAt(0);     
         }
}

Answer 4

Will Sherwood 的回答可能会提供一些细微更改的解决方案，但口头解释这些更改会令人困惑。因此，我实现了 UI 和下面的算法：

public class Minesweeper extends JFrame implements MouseListener {

    // I assume that the grid has to be square (LENGTH*LENGTH)
    private static final int LENGTH = 10, MINE_NUM = 10;
    private static Button[][] buttons = new Button[LENGTH][LENGTH];
    // Stores whether a box holds a mine or not
    private static boolean[][] places;
    // Stores indicator numbers that show how many mines around the box
    private static int[][] indicators;

    public static void main(String[] args) {
        Minesweeper ms = new Minesweeper(LENGTH, LENGTH);
        ms.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
        ms.pack();
        ms.setVisible(true);

        places = getLocationOfMines(LENGTH, MINE_NUM);
        setMineIndicators(places); 
    }

    public Minesweeper(int rows, int cols) {
        Container pane = getContentPane();
        pane.setLayout(new GridLayout(rows, cols));
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                buttons[i][j] = new Button();
                buttons[i][j].addMouseListener(this);
                buttons[i][j].setPreferredSize(new Dimension(30, 30));
                buttons[i][j].setBackground(Color.LIGHT_GRAY);
                pane.add(buttons[i][j]);
            }
        }
    }

    private static boolean[][] getLocationOfMines(int length, int mineNum) {

        boolean[][] places = new boolean [length][length];
        ArrayList<Integer> listX = new ArrayList<Integer>();
        ArrayList<Integer> listY = new ArrayList<Integer>();
        for (int i = 0; i < length; i++) {
            listX.add(new Integer(i));
            listY.add(new Integer(i));
        }

        // Get randomized X, Y indices for hidden mines
        Collections.shuffle(listX);
        Collections.shuffle(listY);
        for (int i = 0; i < mineNum; i++) {
            places[listX.get(i)][listY.get(i)] = true;
        }

        return places;
    }

    private static int[] getButtonIndices(Button button) {
        int[] indices = new int[2];
        for (int i = 0; i < buttons.length; i++) {
            for (int j = 0; j < buttons[i].length; j++) {
                if (buttons[i][j] == button)
                {
                    indices[0] = i;
                    indices[1] = j;
                    return indices;
                }
            }
        }
        return null;
    }

    // Calculates how many mines around the box
    private static void setMineIndicators(boolean[][] places) {
        indicators = new int[places.length][places.length];
        int mineCount = 0;
        for(int i = 0; i < indicators.length; i++) {
            for (int j = 0; j < indicators[i].length; j++) {
                // 00 10 20 
                // 01 11 21
                // 02 12 22
                if (i-1 > -1 && j-1 > -1 && places[i-1][j-1]) {
                    mineCount++;
                }
                if (j-1 > -1 && places[i][j-1]) {
                    mineCount++;
                }
                if (i+1 < indicators.length && j-1 > -1 && places[i+1][j-1]) {
                    mineCount++;
                }
                if (i-1 > -1 && places[i-1][j]) {
                    mineCount++;
                }
                if (i+1 < indicators.length && places[i+1][j]) {
                    mineCount++;
                }
                if (i-1 > -1 && j+1 < indicators.length && places[i-1][j+1]) {
                    mineCount++;
                }
                if (j+1 < indicators.length && places[i][j+1]) {
                    mineCount++;
                }
                if (i+1 < indicators.length && j+1 < indicators.length && places[i+1][j+1]) {
                    mineCount++;
                }

                indicators[i][j] = mineCount;
                mineCount = 0;
            }
        }
    }

    private static void activateMineChain(int x, int y) {
        if (x < 0 || x > LENGTH - 1 || y < 0 || y > LENGTH - 1 || places[x][y] || buttons[x][y].getBackground() == Color.GREEN || indicators[x][y] == -1) {
            return;
        }

        if (indicators[x][y] != 0) {

            buttons[x][y].setLabel("" + indicators[x][y]);
            buttons[x][y].setBackground(Color.ORANGE);

            // If an indicator is visited, do not visit it again
            indicators[x][y] = -1;
            return;
        }

        else if (indicators[x][y] == 0) {
            buttons[x][y].setBackground(Color.YELLOW);
            indicators[x][y] = -1;

            activateMineChain(x, y-1);
            activateMineChain(x-1, y); 
            activateMineChain(x+1, y);
            activateMineChain(x, y+1);

            // Diagonals
            activateMineChain(x-1, y-1);
            activateMineChain(x+1, y-1); 
            activateMineChain(x-1, y+1);
            activateMineChain(x+1, y+1);

            return;
        }
        else {
            return;
        }

    }

    // Check the player is going to win or not (after each green "there is a mine" mark)
    private boolean checkWin() {
        for (int i = 0; i < LENGTH; i++) {
           for (int j = 0; j < LENGTH; j++) {
               if(places[i][j] && !(buttons[i][j].getBackground() == Color.GREEN)) {
                   return false;
               }
           } 
        }
        System.out.println("YOU WIN!");
        for (int i = 0; i < LENGTH; i++) {
           for (int j = 0; j < LENGTH; j++) {
               buttons[i][j].removeMouseListener(this);
           } 
        }
        return true;
    }

    @Override
    public void mouseClicked(MouseEvent me) {

    }

    @Override
    public void mousePressed(MouseEvent me) {
        if (me.getSource() instanceof Button) {
            int[] indices = getButtonIndices((Button) me.getSource());
            if (places[indices[0]][indices[1]] && buttons[indices[0]][indices[1]].getBackground() != Color.GREEN)
            {
                buttons[indices[0]][indices[1]].setBackground(Color.RED);
                System.out.println("YOU LOST!");
                for (int i = 0; i < LENGTH; i++) {
                    for (int j = 0; j < LENGTH; j++) {
                        buttons[i][j].removeMouseListener(this);
                    } 
                }
            }

            else {
                activateMineChain(indices[0], indices[1]);
            }
        }
    }

    // To handle "there is a mine" situation
    @Override
    public void mouseReleased(MouseEvent me) {
        if(SwingUtilities.isRightMouseButton(me)){
            int[] indices = getButtonIndices((Button) me.getSource());

            if (buttons[indices[0]][indices[1]].getBackground() != Color.GREEN) {
                buttons[indices[0]][indices[1]].setBackground(Color.GREEN);
                checkWin();
            }
            else {
                buttons[indices[0]][indices[1]].setBackground(Color.LIGHT_GRAY);
            }
        }
    }

    @Override
    public void mouseEntered(MouseEvent me) {
    }

    @Override
    public void mouseExited(MouseEvent me) {
    }
}

你可以像微软的扫雷一样玩游戏。右键单击以标记矿槽（单击的按钮将变为绿色）并左键单击以打开槽。如果插槽有地雷，它将是红色的。否则，它将是黄色（如果没有指示器）或橙色（如果插槽有显示该插槽周围有多少地雷的指示器编号）。有些部分可能是硬编码的，并且可以轻松地使代码更高效，但我只是展示了我们如何在运行中使用这个算法和 UI。对于那个很抱歉。