MeU的小雪球 @ 2019-04-16 13:29:06
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
int r,c;
int a[102][102];
int minn=9999999,ii,jj;
int s[102][102];
int ans=-1;
bool f[10];
void dfs(int x,int y)
{
for(int i=1;i<=4;i++)f[i]=false;
int t=0,aa,bb;
if(x-1>=1&&a[x-1][y]>a[x][y])//上
{
s[x-1][y]=max(s[x-1][y],s[x][y]+1);
t++;
aa=a[x-1][y];
bb=1;
f[1]=true;
}
if(y-1>=1&&a[x][y-1]>a[x][y])//左
{
s[x][y-1]=max(s[x][y-1],s[x][y]+1);
t++;
if(t==1)
{
aa=a[x][y-1];
bb=2;
}
else if(a[x][y-1]<aa)
{
aa=a[x][y-1];
bb=2;
}
f[2]=true;
}
if(x+1<=r&&a[x+1][y]>a[x][y])//下
{
s[x+1][y]=max(s[x+1][y],s[x][y]+1);
t++;
if(t==1)
{
aa=a[x+1][y];
bb=3;
}
else if(a[x+1][y]<aa)
{
aa=a[x+1][y];
bb=3;
}
f[3]=true;
}
if(y+1<=c&&a[x][y+1]>a[x][y])//右
{
s[x][y+1]=max(s[x][y+1],s[x][y]+1);
t++;
if(t==1)
{
aa=a[x][y+1];
bb=4;
}
else if(a[x][y+1]<aa)
{
aa=a[x][y+1];
bb=4;
}
f[4]=true;
}
if(t==0)return;
else
{
if(bb==1)
{
dfs(x-1,y);
if(f[2])dfs(x,y-1);
if(f[3])dfs(x+1,y);
if(f[4])dfs(x,y+1);
}
else if(bb==2)
{
dfs(x,y-1);
if(f[1])dfs(x-1,y);
if(f[3])dfs(x+1,y);
if(f[4])dfs(x,y+1);
}
else if(bb==3)
{
dfs(x+1,y);
if(f[1])dfs(x-1,y);
if(f[2])dfs(x,y-1);
if(f[4])dfs(x,y+1);
}
else if(bb==4)
{
dfs(x,y+1);
if(f[1])dfs(x-1,y);
if(f[2])dfs(x,y-1);
if(f[3])dfs(x+1,y);
}
return;
}
}
int main()
{
scanf("%d %d",&r,&c);
for(int i=1;i<=r;i++)
{
for(int j=1;j<=c;j++)
{
scanf("%d",&a[i][j]);
if(a[i][j]<minn)//找到其中四周都不能走的
{
minn=a[i][j];
ii=i;
jj=j;
}
}
}
s[ii][jj]=1;
dfs(ii,jj);
for(int i=1;i<=r;i++)
{
for(int j=1;j<=c;j++)
{
if(s[i][j]==0)
{
s[i][j]=1;
dfs(i,j);
}
}
}
for(int i=1;i<=r;i++)
{
for(int j=1;j<=c;j++)
{
ans=max(ans,s[i][j]);
}
}
printf("%d",ans);
return 0;
}
by MeU的小雪球 @ 2019-04-16 13:29:33
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
int r,c;
int a[102][102];
int minn=9999999,ii,jj;
int s[102][102];
int ans=-1;
void dfs(int x,int y)
{
int t=0,aa,bb;
if(x-1>=1&&a[x-1][y]>a[x][y])//上
{
s[x-1][y]=max(s[x-1][y],s[x][y]+1);
t++;
aa=a[x-1][y];
bb=1;
}
if(y-1>=1&&a[x][y-1]>a[x][y])//左
{
s[x][y-1]=max(s[x][y-1],s[x][y]+1);
t++;
if(t==1)
{
aa=a[x][y-1];
bb=2;
}
else if(a[x][y-1]<aa)
{
aa=a[x][y-1];
bb=2;
}
}
if(x+1<=r&&a[x+1][y]>a[x][y])//下
{
s[x+1][y]=max(s[x+1][y],s[x][y]+1);
t++;
if(t==1)
{
aa=a[x+1][y];
bb=3;
}
else if(a[x+1][y]<aa)
{
aa=a[x+1][y];
bb=3;
}
}
if(y+1<=c&&a[x][y+1]>a[x][y])//右
{
s[x][y+1]=max(s[x][y+1],s[x][y]+1);
t++;
if(t==1)
{
aa=a[x][y+1];
bb=4;
}
else if(a[x][y+1]<aa)
{
aa=a[x][y+1];
bb=4;
}
}
if(t==0)return;
else
{
if(bb==1)dfs(x-1,y);
else if(bb==2)dfs(x,y-1);
else if(bb==3)dfs(x+1,y);
else if(bb==4)dfs(x,y+1);
return;
}
}
int main()
{
scanf("%d %d",&r,&c);
for(int i=1;i<=r;i++)
{
for(int j=1;j<=c;j++)
{
scanf("%d",&a[i][j]);
if(a[i][j]<minn)//找到其中四周都不能走的
{
minn=a[i][j];
ii=i;
jj=j;
}
}
}
s[ii][jj]=1;
dfs(ii,jj);
for(int i=1;i<=r;i++)
{
for(int j=1;j<=c;j++)
{
if(s[i][j]==0)
{
s[i][j]=1;
dfs(i,j);
}
}
}
for(int i=1;i<=r;i++)
{
for(int j=1;j<=c;j++)
{
ans=max(ans,s[i][j]);
}
}
printf("%d",ans);
return 0;
}