1 solutions
-
0
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