POJ-1088

25935 단어
//저는 DFS를 사용하고 있는데 DP로 어떻게 해야 할지 아직 생각해 내지 못했습니다. 잠시 DFS로 진행합니다.우선 각 시부터 아래로 수색하면 된다.
코드:
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
#define N 105
int a[N][N];
int dp[N][N];
int vis[N][N];
int dir[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
int m,n;
int dfs(int x,int y)
{
    if(dp[x][y])
    {
        return dp[x][y];
    }
    int cnt=0;
    int i;
    int x1,y1;
    for(i=0;i<4;i++)
    {
        x1=x+dir[i][0];
        y1=y+dir[i][1];
        if(x1>=0&&x1<m&&y1>=0&&y1<n&&a[x][y]>a[x1][y1])
        {
            cnt=max(cnt,dfs(x1,y1));
        }
    }
    dp[x][y]=cnt+1;
    return dp[x][y];
}
int main()
{
    while(scanf("%d%d",&m,&n)!=EOF)
    {
        int i,j;
        for(i=0;i<m;i++)
        {
            for(j=0;j<n;j++)
            {
                scanf("%d",&a[i][j]);
                dp[i][j]=0;
            }
        }
        int h=0;
        for(i=0;i<m;i++)
        {
            for(j=0;j<n;j++)
            {
               h=max(h,dfs(i,j));
            }
        }
        printf("%d
",h); } return 0; }

좋은 웹페이지 즐겨찾기