社区讨论

求助

学术版参与者 2已保存回复 1

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
1 条
当前快照
1 份
快照标识符
@lo2l98ie
此快照首次捕获于
2023/10/23 15:40
2 年前
此快照最后确认于
2023/10/23 15:40
2 年前
查看原帖
已知一个5*11的方格,每个方格有0-1个宝石,求最多能收集宝石的数量以及路径
注:
1.从(1,1)开始,最多走48步
2.只能上下左右走
3.每个格子只能走一次
本人的递归程序极不稳定,快的1s出结果,慢的过了10分钟还在跑,求改进方式(已删除无关部分)
CPP
namespace main_code
{
	const int n=5,m=11;
	int mp[n+1][m+1],book[n+1][m+1];
	int res=0,maxx=0,a[n+1][m+1];
	int fx[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
	void dfs(int x,int y,int z,int s)
	{
		if (z>res||s==48)
		{
			if (z>res)
			{
				res=z;
				IO::cout<<IO::endl<<res<<IO::endl;
				for (int i=1;i<=n;i++)
				{
					for (int j=1;j<=m;j++)
					{
						IO::cout<<(book[i][j]==-1?0:book[i][j])<<' ';
						if (book[i][j]<10) IO::cout<<' ';
					}
					IO::cout<<IO::endl;
				}//每找到更多的就输出
			}
			if (z==maxx)
			{
				system("pause");
				exit(0);
			}
			if (s==48) return;
		}
		for (int i=0;i<4;i++)
		{
			int tx=x+fx[i][0],ty=y+fx[i][1];
			if (tx>=1&&tx<=n&&ty>=1&&ty<=m&&book[tx][ty]==-1)
			{
				book[tx][ty]=s+1;
				dfs(tx,ty,z+mp[tx][ty],s+1);
				book[tx][ty]=-1;
			}
		}
	}
	void main()
	{
		char x;
		for (int i=1;i<=n;i++)
		  for (int j=1;j<=m;j++)
		  {
		  	IO::cin>>x;
		  	mp[i][j]=x-'0';
		  	maxx+=mp[i][j];
		  }
		memset(book,-1,sizeof(book));
		book[1][1]=0;
		dfs(1,1,0,0);
	}
}

回复

1 条回复,欢迎继续交流。

正在加载回复...