萌新求助,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;
}
这是为什么...