View Code of Problem 17

#include<iostream>
#include<algorithm>
#include<memory.h>
using namespace std;
const int maxn=105;
struct Point
{
    Point() {}
    int x,y;
    int heigth;
}a[maxn*maxn];
int dp[maxn*maxn];
bool compare(Point x,Point y)
{
    return x.heigth>y.heigth;
}
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
int main()
{
    //int t;
   // cin>>t;
    int n,m;
    while(cin>>n>>m)
    {
        int ans=0;
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
            {
                cin>>a[i*m+j].heigth;
                a[i*m+j].x=i;
                a[i*m+j].y=j;
                dp[i*m+j]=1;
            }
        }

       /*for(int i=0;i<n*m;i++)
        {
            cout<<a[i].x<<" "<<a[i].y<<endl;
        }*/

        sort(a,a+n*m,compare);

        int x,y;
        int next_x,next_y;
        for(int i=0;i<n*m;i++)
        {
           x=a[i].x;
           y=a[i].y;
           for(int d=0;d<4;d++)
           {
               next_x=x+dx[d];
               next_y=y+dy[d];
               if(next_x>=0&&next_y>=0&&next_x<n&&next_y<m)
               {
                   for(int j=0;j<n*m;j++)
                       if(next_x==a[j].x&&next_y==a[j].y)
                       {
                           if(a[j].heigth<a[i].heigth)
                           {
                               dp[j]=max(dp[i]+1,dp[j]);
                               ans=max(dp[j],ans);
                           }
                           else
                               break;
                       }
               }
           }
        }

        cout<<ans<<endl;
    }

}

Double click to view unformatted code.


Back to problem 17