如何避免此代码中的堆栈溢出，（递归函数）

Question

我正在尝试解决编程竞赛问题。我在这个部门几乎是个菜鸟（我想我有很多东西要学）。我试图解决这个问题，其中包括读取二维数组 (n x m) 并找出其中的斑点。斑点由连续的点亮像素（由 # 表示）形成。不亮像素（由 . 表示）。我试图通过使用递归方法 Blob::form() 来查找 blob。示例输入可能如下所示

1
6 6
#...#.
.#.#.#
##..#.
......
.#.#.#
#...#.

我一时想出了解决办法。而且并不多。但一如既往，它在最坏的情况下失败 n = m = 1000 并且所有字符都是 #。这个的 1000 x 1000 版本：

1
3 3
###
###
###

我假设的问题是堆栈溢出。我发现程序在形成 blob 时崩溃了。

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <algorithm>

using namespace std;
int pat[1000][1000],n,m;
char a[1000][1000];

struct point
{
    int x,y;
};

bool inBounds(point p)
{
    if(p.x < n && p.x >=0 && p.y < m && p.y >= 0) return true;
    else return false;
}
bool isAblob(int i,int j)
{
    point p[8];
    p[0].x = i-1; p[0].y =  j;
    p[1].x = i+1; p[1].y =  j;
    p[2].x = i+1; p[2].y =  j+1;
    p[3].x = i-1; p[3].y =  j-1;
    p[4].x = i-1; p[4].y =  j+1;
    p[5].x = i+1; p[5].y =  j-1;
    p[6].x = i; p[6].y =  j-1;
    p[7].x = i; p[7].y =  j+1;

    for(int k=0;k<8;k++)
    {
        if(inBounds(p[k]))
        {
            if(a[p[k].x][p[k].y] == '#') return true;
        }
    }
    return false;
}


class Blob
{
public:
    long long int pow;

    Blob(int i, int j)
    {
        this->pow = 0;
        point po;
        po.x=i;
        po.y=j;
        this->form(&po);
    }

    int getPow()
    {
        return this->pow;
    }

    void form ( point *p)
    {
        if(inBounds(*p))
        {
            if(a[p->x][p->y] == '#' && !pat[p->x][p->y])
            {
                a[p->x][p->y] = 1;
                this->pow++;
                point *e = new point;
                e->x = p->x-1; e->y =  p->y;if(pat[e->x][e->y] == 0)form(e);
                e->x = p->x+1; e->y =  p->y;if(pat[e->x][e->y] == 0)form(e);
                e->x = p->x+1; e->y =  p->y+1;if(pat[e->x][e->y] == 0)form(e);
                e->x = p->x-1; e->y =  p->y-1;if(pat[e->x][e->y] == 0)form(e);
                e->x = p->x-1; e->y =  p->y+1;if(pat[e->x][e->y] == 0)form(e);
                e->x = p->x+1; e->y =  p->y-1;if(pat[e->x][e->y] == 0)form(e);
                e->x = p->x; e->y =  p->y-1;if(pat[e->x][e->y] == 0)form(e);
                e->x = p->x; e->y =  p->y+1;
                if(pat[e->x][e->y] == 0)form(e);
            }
        }
        return;
    }
};

int main()
{
    int t;

    cin >> t;
    for (int q = 0; q < t; q++)
    {
        cin >> n >> m;
        int bnum = 0;
        Blob *b[(n*m)/2];
        vector <int> pows;
        cin.get();
        for(int i=0;i<n;i++)
        {
            for(int j = 0; j<m;j++)
            {
                a[i][j] = cin.get();
                pat[i][j] = 0;
            }
            cin.get();
        }


        for(int i=0;i<n;i++)
        {
            for(int j = 0; j<m;j++)
            {
                if(a[i][j] == '#' && pat[i][j] == 0)
                {
                    if(isAblob(i,j))
                    {
                        bnum++;
                        b[bnum] = new Blob(i,j);
                        pows.push_back(b[bnum]->getPow());
                    }
                    else continue;
                }
                else continue;
            }
        }
        sort(pows.begin(),pows.end());
        cout << endl << bnum;

        for(int i=1;i<=bnum;i++)
        {
            if(i==1) cout << endl;
            if(i!=1) cout << " ";
            cout << pows[i-1];
        }
    }
}

我确定我的代码有问题且效率低下。我想知道是否有人可以告诉我将来如何避免这些问题。更好的实施也很有帮助。但我正在寻找的是避免将来发生堆栈溢出的技巧。

Answer 1

在我看来，整数矩阵 pat[][] 已初始化为全零，并在多个位置进行了测试，但从未设置为任何其他内容。因此 Blob 构造函数调用 form() 几乎无条件地调用自身，直到发生崩溃。我说 "almost" 是因为还有其他条件导致递归调用，但最后一次检查（pat 中的值）总是成功。

我可能读得太快了，如果是这样，我会谦虚地接受我的打击。 ;-)

Answer 2

在不改变程序逻辑的情况下避免递归的一种简单方法是直接使用堆栈数据结构，而不是通过调用堆栈。

这是您的 Blob class 的修改版本，它在您的表单函数中使用了 std::stack：

class Blob
{
public:
    long long int pow;

    Blob(int i, int j)
    {
        this->pow = 0;
        point po;
        po.x=i;
        po.y=j;
        this->form(po);
    }

    int getPow()
    {
        return this->pow;
    }

    void form (point p)
    {
        std::stack<point> s;
        s.push(p);

        while (!s.empty())
        {
            p=s.top();
            s.pop();

            if (!inBounds(p))
                continue;

            if(a[p.x][p.y] == '#' && !pat[p.x][p.y])
            {
                a[p.x][p.y] = 1;
                this->pow++;
                point e;
                e.x = p.x-1;    e.y =  p.y;     if(pat[e.x][e.y] == 0)s.push(e);
                e.x = p.x+1;    e.y =  p.y;     if(pat[e.x][e.y] == 0)s.push(e);
                e.x = p.x+1;    e.y =  p.y+1;   if(pat[e.x][e.y] == 0)s.push(e);
                e.x = p.x-1;    e.y =  p.y-1;   if(pat[e.x][e.y] == 0)s.push(e);
                e.x = p.x-1;    e.y =  p.y+1;   if(pat[e.x][e.y] == 0)s.push(e);
                e.x = p.x+1;    e.y =  p.y-1;   if(pat[e.x][e.y] == 0)s.push(e);
                e.x = p.x;      e.y =  p.y-1;   if(pat[e.x][e.y] == 0)s.push(e);
                e.x = p.x;      e.y =  p.y+1;   if(pat[e.x][e.y] == 0)s.push(e);
            }

        }
    }
};

请注意，这也会修复您的内存泄漏问题。

一般来说，您要解决的问题似乎是寻找 "connected components" 具有方形邻域的问题。通常，您会使用 disjoint-set data-structure 来解决这个问题，这不需要堆栈或 recursion.With ，您只需扫描一次该字段即可获得所有连接组件的大小，而不是就是你检查斑点的地方。

如何避免此代码中的堆栈溢出，（递归函数）

How to avoid stack overflow in this code, (Recursive function)

c++

stack-overflow

recursion