求助!卡在了一个奇怪的bug...
查看原帖
求助!卡在了一个奇怪的bug...
110119
黑暗中的利剑楼主2025/1/25 18:58

萌新求助,rt,下面代码只有20分,其他全TLE

#include<bits/stdc++.h>
using namespace std;
int n, m, p[1010][1010],maxn,mid,flag,t;
int dx[4]={-1,1,0,0}, dy[4]={0,0,-1,1};
int vis[1010][1010];
void dfs(int i,int j)
{
	if(i==n) {flag=1;return;}
	for(int k=0;k<4;k++) 
	{
		int x=i+dx[k],y=j+dy[k];
		if(x>=1&&x<=n&&y>=1&&y<=m&&p[x][y]<=mid&&!vis[x][y]) 
		{
			vis[x][y]=1;
			dfs(x,y);
			vis[x][y]=0;
			if(flag) break;
		}
	}
}
bool check()
{
	flag=0;
	memset(vis,0,sizeof(vis));
	dfs(1,1);
	if(flag==1)return true;
	return false;
}
int solve(int l,int r)
{
	while(l+1<r)
	{
		mid=(l+r)>>1;
		if(check())r=mid; 
		else l=mid;
	}
	return r;
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			cin>>p[i][j];
			maxn=max(maxn,p[i][j]); 
		}
	}
	cout<<solve(1,maxn);
	return 0;
}

但是,如果把dfs里x,y的定义为全局变量,就会AC...

#include<bits/stdc++.h>
using namespace std;
int n, m, p[1010][1010],maxn,mid,flag,t,x,y;
int dx[4]={-1,1,0,0},dy[4]={0,0,-1,1};
int vis[1010][1010];
void dfs(int i,int j)
{
	if(i==n) {flag=1;return;}
	for(int k=0;k<4;k++) 
	{
		x=i+dx[k],y=j+dy[k];
		if(x>=1&&x<=n&&y>=1&&y<=m&&p[x][y]<=mid&&!vis[x][y]) 
		{
			vis[x][y]=1;
			dfs(x,y);
			vis[x][y]=0;
			if(flag) break;
		}
	}
}
bool check()
{
	flag=0;
	memset(vis,0,sizeof(vis));
	dfs(1,1);
	if(flag==1)return true;
	return false;
}
int solve(int l,int r)
{
	while(l<r)
	{
		mid=(l+r)>>1;
		if(check())r=mid; 
		else l=mid+1;
	}
	return r;
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			cin>>p[i][j];
			maxn=max(maxn,p[i][j]); 
		}
	}
	cout<<solve(1,maxn);
	return 0;
}

这是为什么...

2025/1/25 18:58
加载中...