萌新刚学OI求助,关于搜索
  • 板块学术版
  • 楼主断清秋
  • 当前回复9
  • 已保存回复9
  • 发布时间2021/11/19 20:09
  • 上次更新2023/11/4 00:06:55
查看原帖
萌新刚学OI求助,关于搜索
93266
断清秋楼主2021/11/19 20:09

RT,为什么改变 dx,dy 方向数组的元素顺序会导致结果不同?

int dx[3]={-1,0,1},dy[3]={0,1,0};
bool vis[1005][1005];
void dfs(int x,int y,ll ans)
{
	if(x==n&&y==m)
	{
		if(fd[x][y]>=ans)
			back ;
		res=max(ans,res);
		back ;
	}
	if(vis[x][y])
		back ;
	vis[x][y]=1;
	if(vis[x-1][y]||(x==1&&!vis[x+1][y]))
	{
		if(fd[x][y]>=ans)
			back ;
		fd[x][y]=ans;
	}
	if(vis[x+1][y]||(x==n&&!vis[x-1][y]))
	{
		if(fu[x][y]>=ans)
			back ;
		fu[x][y]=ans;
	}
	for(ri i=0;i<=2;i++)
	{
		int xx=x+dx[i],yy=y+dy[i];
		if(xx>=1&&xx<=n&&yy>=1&&yy<=m)
			dfs(xx,yy,ans+a[xx][yy]);
	}
	vis[x][y]=0;
}

int dx[3]={-1,1,0},dy[3]={0,0,1};
bool vis[1005][1005];
void dfs(int x,int y,ll ans)
{
	if(x==n&&y==m)
	{
		if(fd[x][y]>=ans)
			back ;
		res=max(ans,res);
		back ;
	}
	if(vis[x][y])
		back ;
	vis[x][y]=1;
	if(vis[x-1][y]||(x==1&&!vis[x+1][y]))
	{
		if(fd[x][y]>=ans)
			back ;
		fd[x][y]=ans;
	}
	if(vis[x+1][y]||(x==n&&!vis[x-1][y]))
	{
		if(fu[x][y]>=ans)
			back ;
		fu[x][y]=ans;
	}
	for(ri i=0;i<=2;i++)
	{
		int xx=x+dx[i],yy=y+dy[i];
		if(xx>=1&&xx<=n&&yy>=1&&yy<=m)
			dfs(xx,yy,ans+a[xx][yy]);
	}
	vis[x][y]=0;
}

这两份代码只是换了方向数组的顺序,为什么运行结果会不同?

2021/11/19 20:09
加载中...