c++ - 扫雷。递归检查时的段错误

Question

我正在尝试在 C++11 中使用 Qt 编写扫雷程序。

如果我按下一个带有 0 个炸弹的按钮，我想检查这个按钮周围的按钮以及它们是否也有 0 个炸弹。如果他们有 0 颗炸弹，我想检查按钮。 (图:红色方 block )

这是我的按钮类:

#ifndef ABUTTON_H
#define ABUTTON_H

#include "QPushButton"
#include "QMouseEvent"

class AButton : public QPushButton
{
    Q_OBJECT                    

public:
    AButton(QWidget* parent);
    //AButton();
    ~AButton();
    bool& set(bool state);          //set bomb state
    bool get();                 //get bomb state    
    void increment_counter();           //increment counter for surrounding bombs
    int get_counter();              //get bomb counter
    bool get_locked();              //is it locked (->flagged)
    void set_locked(bool);          //set it to locked
    AButton* get_Button(char c);        //get Button above, beneath, left, right
    void set_Button(AButton* Button, char c);   //set Button above, ...; char is for setting the right one
private:
    bool bomb;                  //is button a bomb
    int Nachbar_Bomben;             // how many bombs around this button
    bool locked;                // is the button locked
    AButton* b_links;               //pointer to the button to the left
    AButton* b_rechts;              //pointer to the button to the right
    AButton* b_oben;                //pointer to the button above
    AButton* b_unten;               //pointer to the button beneath

public slots:
    void mousePressEvent(QMouseEvent *event);

signals:
    void rightclicked();
    void leftclicked();

};

#endif // ABUTTON_H

这是点击按钮时发生的情况:

    void Layout::ButtonClicked()
    {

    char Buffer [50];

    AButton *clickedButton = qobject_cast <AButton*>(sender());         //which button

    if (!clickedButton->get_locked())
    {
    clickedButton->setChecked(1);                           //set button to checked
    {
    if (clickedButton->get())                                   //Is button a bomb?
    {
        clickedButton->setText(QString ("B"));
        Fehlermeldung *Fehler = new Fehlermeldung();            //make error window
        Fehler->show();
    }
    else
    {
        if(clickedButton->get_counter() == 0)                       //has this button 0 bombs?
        {
            check_for_surrounding_bombs(clickedButton);             //start the recursiv check, if there are buttons with 0 bombs around
        }
        else
        {
        sprintf(Buffer, "%i", clickedButton->get_counter());
        clickedButton->setText(QString (Buffer));                       //write how many bombs are in this button

     }}}}}

我的问题是，我通过调用函数“check_for_surrounding_bombs”得到了一个段错误。

void Layout::check_for_surrounding_bombs(AButton* clickedButton)        //function doesnt work
{
    if (clickedButton->get_Button('o'))                                 //does the button above exist?
    {
    if (clickedButton->get_Button('o')->get_counter()== 0)              //has this button 0 bombs
    {
        clickedButton->get_Button('o')->setText(QString (""));          // write nothing in it

        if (!clickedButton->get_Button('o')->get_locked())              //if it isnt locked (= set flag)
        {
                 clickedButton->get_Button('o')->setChecked(1);               //set the button to checked
        }
        check_for_surrounding_bombs(clickedButton->get_Button('o'));            //do the same thing for the button above

    }
//... the function does the same with the buttons to the left, right, beneath

我不确定我的递归方法是否正确。

调试器在调用函数“check_for_surrounding_bombs(clickedButton);”时给我这个错误:

enter image description here

get_Button 成员 fct 的实现。

AButton* AButton::get_Button(char c)
{
    if (c == 'o')
    return b_oben;      //return button above
    else if (c == 'u')
    return b_unten;     //return button beneath
    else if (c == 'l')
    return b_links;     //return button to the left
    else if (c == 'r')
    return b_rechts;    //return button to the right
    else
    return 0;
}

有什么想法吗？

提前谢谢你。

Answer 1

崩溃可能是由堆栈溢出引起的。发生这种情况是因为您的递归解决方案没有简化问题的机制。

如果您在递归之前更改您访问过的每个按钮的状态，那么问题就会变得有界并且您的问题大部分都会消失。

递归解决方案中的每个步骤都需要一些堆栈。这是一个相对有限的资源，因为堆栈有一个界限，并且不能增长到用于其他目的的内存中。因此，在这种情况下，如果您有一个包含 100x100 个元素的网格布局，则可能有 10,000 个步骤。

因此，我会考虑另一种非递归解决方案，您可以在其中创建一个 vector 或要访问的项目列表，然后向其中添加项目。

还是有必要的

1. 不要将一个位置添加到列表中两次。
2. 访问过某个地点后，不要再次访问该地点。