Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 小白记忆话搜索练习

Posted by xsjlmzs at 2018-03-28 16:51:57 on Problem 1088
```开始以为广搜一下就可一乐，后来发现自己太naive了。。。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<queue>
#include<utility>
using namespace std;
int arr[105][105];
int dp[105][105]={-1};
int n,m;
int mx(int a,int b,int c,int d)
{
int temp=0;
if(a>temp)
temp=a;
if(b>temp)
temp=b;
if(c>temp)
temp=c;
if(d>temp)
temp=d;
return temp;
}
int res(int x,int y)
{
int a=0,b=0,c=0,d=0;
if(dp[x][y]>0)
return dp[x][y];
if(x>n||x<=0||y<=0||y>m)
return 0;
else if(arr[x-1][y]>=arr[x][y]&&arr[x+1][y]>=arr[x][y]&&arr[x][y-1]>=arr[x][y]&&arr[x][y+1]>=arr[x][y])
return dp[x][y]=0;
else
{
if(arr[x+1][y]<arr[x][y])
a=res(x+1,y);
if(arr[x-1][y]<arr[x][y])
b=res(x-1,y);
if(arr[x][y+1]<arr[x][y])
c=res(x,y+1);
if(arr[x][y-1]<arr[x][y])
d=res(x,y-1);
}
return dp[x][y]=mx(a,b,c,d)+1;
}
int main(void)
{
while(scanf("%d%d",&n,&m)==2)
{
memset(dp,0,sizeof(dp));
memset(arr,0x3f,sizeof(arr));
for(int i=1; i<=n; ++i)
{
for(int j=1; j<=m; ++j)
scanf("%d",&arr[i][j]);
}
int mn=-99;
for(int i=1; i<=n; ++i)
{
for(int j=1; j<=m; ++j)
{
int temp=res(i,j);
mn=max(mn,temp);
}
}
printf("%d\n",mn+1);
}
return 0;
}
```

Followed by:

User ID:
Title:

Content: