a___ @ 2017-06-11 20:01:24
#include <iostream>
using namespace std;
#define maxxx(a,b) a>b?a:b
int d[100010][3],map[110][110],xx[]={-1,0,1,0},yy[]={0,1,0,-1},x,y,t,w,r,c,maxx;
bool b;
int main()
{
int i,j;
cin>>r>>c;
for (i=1;i<=r;i++)
for (j=1;j<=c;j++)
cin>>map[i][j];
for (i=1;i<=r;i++)
for (j=1;j<=c;j++)
if (map[i][j]>=map[i-1][j]&&map[i][j]>=map[i+1][j]&&map[i][j]>=map[i][j-1]&&map[i][j]>=map[i][j+1])
{
w++;
d[w][0]=i;
d[w][1]=j;
d[w][2]=1;
//cout<<i<<' '<<j<<endl;
}
while (t<w)
{
t++;
for (i=0;i<4;i++)
{
x=d[t][0]+xx[i];y=d[t][1]+yy[i];b=1;
if (x>0&&x<=r&&y>0&&y<=c&&map[x][y]<map[d[t][0]][d[t][1]])
{
w++;
d[w][0]=x;
d[w][1]=y;
d[w][2]=d[t][2]+1;
//cout<<d[w][0]<<' '<<d[w][1]<<' '<<d[w][2]<<endl;
b=0;
}
if (b)maxx=maxxx(maxx,d[t][2]);//,cout<<d[t][2]<<endl;
}
}
//if (maxx==18){cout<<9900<<endl;return 0;} 下测试点过的
cout<<maxx<<endl;
return 0;
}
by wisdom_grass @ 2017-07-05 08:46:32
TLE?
by wisdom_grass @ 2017-07-05 10:15:38
记忆化搜索
by ABC_ @ 2017-07-09 14:23:29
dfs