1 solutions

  • 0
    @ 2024-12-11 0:49:30

    C :

    #include <stdio.h>
    int a[101][101],f[101][101],r,c;
    int dfs(int i,int j)
    {
        int max,t;
        if (f[i][j]!=-1) return f[i][j];
        max=0;
        if (j>1 && a[i][j]>a[i][j-1])
        {
            t=dfs(i,j-1);
            if (max<t) max=t;
        }
        if (j<c && a[i][j]>a[i][j+1])
        {
            t=dfs(i,j+1);
            if (max<t) max=t;
        }
        if (i>1 && a[i][j]>a[i-1][j])
        {
            t=dfs(i-1,j);
            if (max<t) max=t;
        }
        if (i<r && a[i][j]>a[i+1][j])
        {
            t=dfs(i+1,j);
            if (max<t) max=t;
        }
        f[i][j]=max+1;
        return f[i][j];
    }
    int main()
    {
        int i,j,max;
        scanf("%d%d",&r,&c);
        for (i=1;i<=r;i++)
            for (j=1;j<=c;j++)
            {
                scanf("%d",&a[i][j]);
                f[i][j]=-1;
            }
        max=-1;
        for (i=1;i<=r;i++)
            for (j=1;j<=c;j++)
            if (dfs(i,j)>max) max=dfs(i,j);
        printf("%d",max);
        return 0;
    }
    
    

    C++ :

     #include<iostream>
      using namespace std;
      const int maxn=100,maxm=100;
      const int dirx[4]={0,0,1,-1};
      const int diry[4]={1,-1,0,0};
      int n,m,maxx=0;
      int a[maxn][maxm],dis[maxn][maxm]={0};
      
      void get_input()
     {     cin >> n >> m;
         for (int i=0;i<n;i++){
             for (int j=0;j<m;j++) cin >> a[i][j];
         }
     }
     void dfs(int x,int y,int depth)
     {
         int nowdepth=depth;
        if ((++nowdepth)>dis[x][y]){ 
             dis[x][y]=nowdepth;
             if (dis[x][y]>maxx) maxx=dis[x][y];
         }
         else return;
         int nowx,nowy;
        for (int i=0;i<4;i++){
             nowx=x+dirx[i];nowy=y+diry[i];
             if (nowx<0 || nowx>=n || nowy<0 || nowy>=m) continue;
             if (a[nowx][nowy] <= a[x][y])continue;  
             dfs(nowx,nowy,nowdepth);
         }
     }
     int main()
     {
         get_input();
         for (int i=0;i<n;i++){
             for (int j=0;j<m;j++) if (dis[i][j]==0)dfs(i,j,0);
        }
         cout << maxx << endl;
         return 0;
     }
    

    Pascal :

    var
       i,j,n,m,max,t:longint;
       a,f:array[0..1000,0..1000] of longint;
       b,x,y:array[0..10000] of longint;
    procedure qsort(l,r:longint);
    var
        i,j,mid:longint;
    begin
     i:=l;j:=r;
     mid:=b[(l+r)>>1];
     while i<=j do
      begin
       while (b[i]<mid) do inc(i);
       while (b[j]>mid) do dec(j);
       if i<=j then
        begin
         t:=b[i];b[i]:=b[j];b[j]:=t;
         t:=x[i];x[i]:=x[j];x[j]:=t;
         t:=y[i];y[i]:=y[j];y[j]:=t;
         inc(i);dec(j);
        end;
      end;
     if j>l then qsort(l,j);
     if i<r then qsort(i,r);
    end;
    begin
     readln(n,m);
     for i:=1 to n do
      for j:=1 to m do
       begin
        read(a[i,j]);
        b[i*m-m+j]:=a[i,j];
        x[i*m-m+j]:=i;
        y[i*m-m+j]:=j;
        f[i,j]:=1;
       end;
     qsort(1,n*m);
     max:=-maxlongint;
     for i:=1 to n*m do
      begin
       if (x[i]>1)and(a[x[i],y[i]]>a[x[i]-1,y[i]])and(f[x[i],y[i]]<f[x[i]-1,y[i]]+1)
        then f[x[i],y[i]]:=f[x[i]-1,y[i]]+1;
       if (x[i]<n)and(a[x[i],y[i]]>a[x[i]+1,y[i]])and(f[x[i],y[i]]<f[x[i]+1,y[i]]+1)
        then f[x[i],y[i]]:=f[x[i]+1,y[i]]+1;
       if (y[i]>1)and(a[x[i],y[i]]>a[x[i],y[i]-1])and(f[x[i],y[i]]<f[x[i],y[i]-1]+1)
        then f[x[i],y[i]]:=f[x[i],y[i]-1]+1;
       if (y[i]<m)and(a[x[i],y[i]]>a[x[i],y[i]+1])and(f[x[i],y[i]]<f[x[i],y[i]+1]+1)
        then f[x[i],y[i]]:=f[x[i],y[i]+1]+1;
       if max<f[x[i],y[i]] then max:=f[x[i],y[i]];
      end;
     writeln(max);
    end.
    

    Python :

    # coding=utf-8
    MAX = 101
    
    def update(x, y):
        if x > 1 and h[x][y] > h[x - 1][y]:
            ans[x][y] = max(ans[x][y], ans[x - 1][y] + 1)
        if y > 1 and h[x][y] > h[x][y - 1]:
            ans[x][y] = max(ans[x][y], ans[x][y - 1] + 1)
        if x < r and h[x][y] > h[x + 1][y]:
            ans[x][y] = max(ans[x][y], ans[x + 1][y] + 1)
        if y < c and h[x][y] > h[x][y + 1]:
            ans[x][y] = max(ans[x][y], ans[x][y + 1] + 1)
    
    while True:
        try:
            r, c = map(int, input().split())
        except EOFError:
            break
        
        h = [[0] * MAX for _ in range(MAX)]
        ans = [[1] * MAX for _ in range(MAX)]
        v = []
        for i in range(1, r+1):
            line = list(map(int, input().split()))
            for j in range(1, c+1):
                h[i][j] = line[j-1]
                v.append((i, j, h[i][j]))
        v.sort(key=lambda x: x[2])
        for x, y, value in v:
            update(x, y)
        result = max(max(ans, key=max))
        print(result)
    
    
    • 1

    Information

    ID
    756
    Time
    1000ms
    Memory
    128MiB
    Difficulty
    (None)
    Tags
    # Submissions
    0
    Accepted
    0
    Uploaded By