C++ 手工栈 解决递归次数太多爆栈的问题

发布于 2019-04-05  16 次阅读


首先我们有一个搜索的题目,源程序如下

#include
using namespace std;
int a[1001][1001],dx[4],dy[4];
bool f[1001][1001],up,down;
int n,m;
int init()
{
    dx[1]=1; dx[2]=0; dx[3]=-1; dx[4]=0;
    dy[1]=0; dy[2]=1; dy[3]=0; dy[4]=-1;  
}
int dfs(int x,int y,int z)
{
    int i,j,k;
    f[x][y]=true;
    for (i=1;i<=4;i++)
      if (x+dx[i]>=1&&x+dx[i]<=n&&y+dy[i]>=1&&y+dy[i]<=m)
        {
          if (a[x+dx[i]][y+dy[i]]=1&&x+dx[i]<=n&&y+dy[i]>=1&&y+dy[i]<=m&&f[x+dx[i]][y+dy[i]]==false&&a[x+dx[i]][y+dy[i]]==z)
        dfs(x+dx[i],y+dy[i],z);
    return 0;
}
int main()
{
    freopen("seek.in", "r", stdin);
    freopen("seek.out", "w", stdout);

    int i,j,k,s,u,d;
    init();

    scanf("%d%d",&n,&m);
    for (i=1;i<=n;i++)
      for (j=1;j<=m;j++)
      {
          scanf("%d",&a[i][j]);
          f[i][j]=false;
      }

    u=0; d=0;
    for (i=1;i<=n;i++)
      for (j=1;j<=m;j++)
      {
          up=false;
          down=false;
          if (f[i][j]==false) dfs(i,j,a[i][j]);
          if (up==true&&down==false) u++;
          else if (up==false&&down==true) d++;
      }
    printf("%d %d",u,d);
    return 0;
}

这个程序运行到到一定的数量时会爆栈,所以我们就有一种开手工栈的方法,人为将栈的大小变大
像这样

    int size = 256 << 20; //250M
    char*p=(char*)malloc(size) + size;
    __asm__("movl %0, %%esp\n" :: "r"(p) );

这个就是讲栈开到250M,但是有要注意的地方,首先要调用

#include

不然第二行会报错,然后我们要将这一部分的东西放入主程序的最前端,就可以了
成品如下

#include
#include
using namespace std;
int a[1001][1001],dx[4],dy[4];
bool f[1001][1001],up,down;
int n,m;
int init()
{
    dx[1]=1; dx[2]=0; dx[3]=-1; dx[4]=0;
    dy[1]=0; dy[2]=1; dy[3]=0; dy[4]=-1;  
}
int dfs(int x,int y,int z)
{
    int i,j,k;
    f[x][y]=true;
    for (i=1;i<=4;i++)
      if (x+dx[i]>=1&&x+dx[i]<=n&&y+dy[i]>=1&&y+dy[i]<=m)
        {
          if (a[x+dx[i]][y+dy[i]]=1&&x+dx[i]<=n&&y+dy[i]>=1&&y+dy[i]<=m&&f[x+dx[i]][y+dy[i]]==false&&a[x+dx[i]][y+dy[i]]==z)
        dfs(x+dx[i],y+dy[i],z);
    return 0;
}
int main()
{
    int size = 256 << 20; 
    char*p=(char*)malloc(size) + size;
    __asm__("movl %0, %%esp\n" :: "r"(p) );
    freopen("seek.in", "r", stdin);
    freopen("seek.out", "w", stdout);

    int i,j,k,s,u,d;
    init();

    scanf("%d%d",&n,&m);
    for (i=1;i<=n;i++)
      for (j=1;j<=m;j++)
      {
          scanf("%d",&a[i][j]);
          f[i][j]=false;
      }

    u=0; d=0;
    for (i=1;i<=n;i++)
      for (j=1;j<=m;j++)
      {
          up=false;
          down=false;
          if (f[i][j]==false) dfs(i,j,a[i][j]);
          if (up==true&&down==false) u++;
          else if (up==false&&down==true) d++;
      }
    printf("%d %d",u,d);
    return 0;
}

然后按理论上来说是不会再爆栈了,但是有一些题库会不支持,所以推荐仅供平时练习时用。

]]>