首先我们有一个搜索的题目,源程序如下
#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;
}
然后按理论上来说是不会再爆栈了,但是有一些题库会不支持,所以推荐仅供平时练习时用。
Comments NOTHING