我正在编写用于扫雷游戏游戏的递归方法,并且我正在遇到递归方法中的堆叠率错误,以清除空空间,在检查周围的3个时不会发生错误空间,但仅在检查全部八个时。您可以帮助确定这个问题吗?
堆栈跟踪是:
Exception in thread "AWT-EventQueue-0" java.lang.StackOverflowError
at java.awt.Component.firePropertyChange(Component.java:8419)
at javax.swing.AbstractButton.setText(AbstractButton.java:306)
at Minesweeper.Minesweeper.showTile(Minesweeper.java:105)
at Minesweeper.Minesweeper.clearEmpty(Minesweeper.java:137)
at Minesweeper.Minesweeper.clearEmpty(Minesweeper.java:177)
类:
public class Minesweeper implements ActionListener {
JFrame frame = new JFrame("Minesweeper");
JButton reset = new JButton("Reset");
JButton solve = new JButton("Solve");
JToggleButton[][] buttons = new JToggleButton[20][20];
int[][] counts = new int [20][20];
Container grid = new Container();
final int MINE = 10;
public static void main(String[] args)
{
new Minesweeper();
}
public Minesweeper()
{
frame.setSize(600, 600);
frame.setLayout(new BorderLayout());
frame.add(reset, BorderLayout.NORTH);
frame.add(solve, BorderLayout.SOUTH);
reset.addActionListener(this);
solve.addActionListener(this);
grid.setLayout(new GridLayout(20, 20));
for (int r = 0; r < buttons.length; r++) {
for (int c = 0; c < buttons[0].length; c++) {
buttons[r][c] = new JToggleButton();
buttons[r][c].addActionListener(this);
grid.add(buttons[r][c]);
buttons[r][c].setSize(frame.getWidth() / 20, frame.getHeight() / 22);
}
}
frame.add(grid,BorderLayout.CENTER);
addRandomMines();
frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
frame.setVisible(true);
}
public void addRandomMines()
{
ArrayList<Integer> mineList = new ArrayList<Integer>();
for (int x = 0; x < counts.length; x++) {
for (int y = 0; y < counts[0].length; y++){
mineList.add((x*100)+y);
}
}
counts = new int[20][20];
for (int i = 0; i < 30; i++) {
int choice = (int)(Math.random()*mineList.size());
counts[mineList.get(choice)/100][mineList.get(choice)%100] = MINE;
mineList.remove(choice);
}
for (int x = 0; x < counts.length; x++) {
for (int y = 0; y < counts[0].length; y++){
if (counts[x][y]!=MINE) {
int mineCount = 0;
if (x > 0 && y > 0 && counts[x - 1][y - 1] == MINE)
mineCount++;
if (y > 0 && counts[x][y - 1] == MINE)
mineCount++;
if (x > 0 && counts[x - 1][y] == MINE)
mineCount++;
if (x < counts.length - 1 && counts[x + 1][y] == MINE)
mineCount++;
if (y < counts.length - 1 && counts[x][y + 1] == MINE)
mineCount++;
if (x < counts.length - 1 && y < counts.length - 1 && counts[x + 1][y + 1] == MINE)
mineCount++;
if (x > 0 && y < counts.length - 1 && counts[x - 1][y + 1] == MINE)
mineCount++;
if (x < counts.length - 1 && y > 0 && counts[x + 1][y - 1] == MINE)
mineCount++;
counts[x][y] = mineCount;
}
}
}
}
public void showTile(int r, int c)
{
if (counts[r][c] == 0) {
buttons[r][c].setText("");
buttons[r][c].setSelected(true);
}
else if (counts[r][c]==MINE) {
buttons[r][c].setForeground(Color.red);
buttons[r][c].setText("X");
buttons[r][c].setSelected(true);
}
else {
buttons[r][c].setText(counts[r][c] + "");
if (counts[r][c]==1)
buttons[r][c].setForeground(Color.blue);
else if (counts[r][c]==2)
buttons[r][c].setForeground(Color.magenta);
else if (counts[r][c]==3)
buttons[r][c].setForeground(Color.green);
buttons[r][c].setSelected(true);
}
}
public void lostGame() {
for (int x = 0; x < buttons.length; x++) {
for (int y = 0; y < buttons[0].length; y++) {
if (counts[x][y]==MINE) {
showTile(x, y);
}
}
}
}
public void clearEmpty(ArrayList<Integer> toClear)
{
if (toClear.size()==0){
return;
}
else {
int x = toClear.get(0)/100;
int y = toClear.get(0)%100;
toClear.remove(0);
if (counts[x][y]==0) {
if (x > 0 && y > 0) {
showTile(x-1,y-1);
if (counts[x-1][y-1]==0)
toClear.add((x-1)*100 + (y-1));
}
if (y > 0) {
showTile(x,y-1);
if (counts[x][y-1]==0)
toClear.add(x*100 + (y-1));
}
if (x <counts.length-1 && y > 0) {
showTile(x+1,y-1);
if (counts[x+1][y-1]==0)
toClear.add((x+1)*100 + (y-1));
}
if (x > 0) {
showTile(x-1,y);
if (counts[x-1][y]==0)
toClear.add((x-1)*100 + y);
}
if (x <counts.length-1 && y > 0) {
showTile(x+1,y);
if (counts[x+1][y]==0)
toClear.add((x+1)*100 + y);
}
if (x > 0 && y < counts[0].length-1) {
showTile(x-1,y+1);
if (counts[x-1][y+1]==0)
toClear.add((x-1)*100 + (y+1));
}
if (y < counts[0].length-1) {
showTile(x,y+1);
if (counts[x][y+1]==0)
toClear.add(x*100 + (y+1));
}
if (x <counts.length-1 && y < counts[0].length-1) {
showTile(x+1,y+1);
if (counts[x+1][y+1]==0)
toClear.add((x+1)*100 + (y+1));
}
}
clearEmpty(toClear);
}
}
@Override
public void actionPerformed(ActionEvent event) {
if (event.getSource().equals(reset)) {
for (int r = 0; r < buttons.length; r++) {
for (int c = 0; c < buttons[0].length; c++) {
buttons[r][c].setSelected(false);
buttons[r][c].setText("");
}
}
addRandomMines();
} else if (event.getSource().equals(solve)) {
} else {
for (int r = 0; r < buttons.length; r++) {
for (int c = 0; c < buttons[0].length; c++) {
if (event.getSource().equals(buttons[r][c])) {
if (counts[r][c] == MINE) {
showTile(r, c);
lostGame();
}
else if (counts[r][c] == 0) {
ArrayList<Integer> toClear = new ArrayList<Integer>();
toClear.add(r*100+c);
clearEmpty(toClear);
}
else {
showTile(r, c);
}
}
}
}
}
}
}
我认为您正在使用错误的算法...
尝试使用迭代而不是递归方法。
正如User404已经提到的当前算法保持列表的增长...
用于实施:您有400个瓷砖。假设(最坏的情况)所有瓷砖都是空的,您一次调用您的方法clearEmpty()
。您会发现所有8个邻居都是空的,因此您将这8个邻居添加到列表中,而仅删除第一个邻居。现在,您将数组再次转到方法(第二个调用),并将再次找到8个邻居以进行第一个条目。因此,您的第三个电话将有15个瓷砖的列表。
真正的问题
这样,您将永远不会结束,因为您永远不会检查当前检查的瓷砖是否已经清除,但您只添加到列表中的删除多于您的删除。
解决方案
至少您应该检查要添加到列表中的瓷砖是否已经清除或已经在列表中。
您的例子是一个很明显的例子,为什么应谨慎使用递归算法,因为有时终止很困难,而且您也必须注意任何工作要多次完成。