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

Re:为什么要递归呢 直接数长度是不是更简单 ?

Posted by whxc049 at 2015-08-01 20:51:34 on Problem 1088
In Reply To:为什么要递归呢 直接数长度是不是更简单 ? Posted by:KoB at 2015-07-14 11:59:18
```> // 懒 于是直接数长度 从大到小数完了事
> // 同上 于是没优化 渣代码 希望还能读
>
> #include <cstdio>
> #include <cstring>
> #include <algorithm>
>
> struct Pos {
>         int val;
>         int u;
>         int v;
>         Pos() {}
>         Pos(int _val, int _u, int _v) : val(_val), u(_u), v(_v) {}
> };
>
> int cmp(Pos a, Pos b) { return a.val > b.val; }
>
> int main() {
>         int row, col;
>         scanf("%d %d", &row, &col);
>         int mat[row][col];
>         for (int i=0; i<row; i++)
>                 for (int j=0; j<col; j++)
>                         scanf("%d", &(mat[i][j]));
>
>         Pos pos[row*col];
>         for (int i=0; i<row; i++)
>                 for (int j=0; j<col; j++)
>                         pos[i*col+j] = Pos(mat[i][j], i, j);
>
>         std::sort(pos, pos+row*col, cmp);
>
>         int dist[row][col];
>         memset(dist, 0, sizeof(dist));
>
>         for (int it=0; it<row*col; it++) {
>                 int i = pos[it].u;
>                 int j = pos[it].v;
>                 if (i != 0       && mat[i][j] > mat[i-1][j]) dist[i-1][j] = std::max(dist[i-1][j], dist[i][j] + 1);
>                 if (i != row - 1 && mat[i][j] > mat[i+1][j]) dist[i+1][j] = std::max(dist[i+1][j], dist[i][j] + 1);
>                 if (j != 0       && mat[i][j] > mat[i][j-1]) dist[i][j-1] = std::max(dist[i][j-1], dist[i][j] + 1);
>                 if (j != col - 1 && mat[i][j] > mat[i][j+1]) dist[i][j+1] = std::max(dist[i][j+1], dist[i][j] + 1);
>         }
>
>         int length = 0;
>         for (int i=0; i<row; i++)
>                 for (int j=0; j<col; j++)
>                         if (dist[i][j] > length)
>                                 length = dist[i][j];
>
>         printf("%d\n", length+1);
>
>         return 0;
> }
```

Followed by: