如何修改才能不让程序中的递归爆掉
查看原帖
如何修改才能不让程序中的递归爆掉
312780
456laji楼主2020/6/2 19:14

我这样只能得到62分,我下载一个测试点,我才知道是我的递归爆掉了,我调试了好久,一直没有办法让它不爆掉,所以求组大佬们,要如何修改。

#include<bits/stdc++.h>
using namespace std;
const int N= 1000+10;
const int INF=0x7f7f7f7f;
int mp[N][N],vis[N][N];
int d[][2]={{1,0},{0,1},{-1,0},{0,-1}};
int n,cnt=INF,c=0,res;

inline int read()
{
	int x=0,f=1;
	char c=getchar();
	while(c>'9'||c<'0')
	{
		if(c=='-') f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9')
	{
		x=x*10+c-'0';
		c=getchar();
	}
	return x*f;
}

void dfs(int x,int y,int t)
{
	//printf("%d %d %d \n",x,y,t);
	if((mp[x][y]!=-1&&t>=mp[x][y])||t>cnt)	return ;
	if(mp[x][y]==-1)
	{//printf("     x=%d y=%d t=%d  c=%d\n",x,y,t,c);
		cnt=min(cnt,t);
		res=cnt;
		return ;
	}
	
	for(int i=0;i<4;i++)
	{
		int dx=x+d[i][0];
		int dy=y+d[i][1];
		if(vis[dx][dy]==0&&dx>=0&&dx<n&&dy>=0&&dy<n)
		{
			vis[x][y]=1;
			t+=1;
			dfs(dx,dy,t);
			vis[x][y]=0;
			t-=1;
		}
	}
}

int main()
{
	int m;
	scanf("%d",&n);
	for(int i=0;i<=n;i++)
		for(int j=0;j<=n;j++)
			mp[i][j]=-1;
		
	for(int i=1;i<=n;i++)
	{
		int a,b,v;
		scanf("%d%d%d",&a,&b,&v);
		if(mp[a][b]==-1) mp[a][b]=v;	
		else mp[a][b]=min(mp[a][b],v);
		for(int k=0;k<4;k++)
		{
			int dx=a+d[k][0];
			int dy=b+d[k][1];
			if(dx>=0&&dx<n&&dy>=0&&dy<n)
			{
				if(mp[dx][dy]!=-1) mp[dx][dy]=min(mp[dx][dy],v);
				else mp[dx][dy]=v;
			}
		}
	}
	/*for(int i=0;i<n;i++)
	{
		for(int j=0;j<n;j++)
			printf("%2d ",mp[i][j]);
		printf("\n");
	}*/
	dfs(0,0,0);
	if(cnt>=(n*n)||cnt==0) printf("-1\n");
	else printf("%d\n",cnt);
	return 0;
}

码风丑陋,见谅。

2020/6/2 19:14
加载中...