社区讨论
求助
学术版参与者 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分钟还在跑,求改进方式(已删除无关部分)
CPPnamespace 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 条回复,欢迎继续交流。
正在加载回复...