学步园

第七章的熟悉的味道，加上第九章一开始的嵌套正方形

因为终点不固定，似乎不方便递推

最后求所有出发点的dp值的最大值。

Run Time: 0.022s

#define UVa  "9-1.10285.cpp"		//Longest Run on a Snowboard
char fileIn[30] = UVa, fileOut[30] = UVa;

#include<cstring>
#include<cstdio>
#include<algorithm>

using namespace std;


//Global Variables. Reset upon Each Case!
const int maxr = 100 + 5, maxc = 100 + 5, maxs = 1000 + 5;
int step[2][4] = {{-1, 0, 1, 0},{0, 1, 0, -1}};
int N, R, C;
char name[maxs];
int G[maxr][maxc];
int d[maxr][maxc];
int vis[maxr][maxc];
/////

int inside(int r, int c) {
    return (r >= 0 && r < R && c >= 0 && c < C);
}
int downward(int r, int c, int vr, int vc) {
    return G[vr][vc] < G[r][c];Longest Run on a Snowboard
}

int dp(int r, int c) {
    int& ans = d[r][c];
    if(vis[r][c] == N) return ans;
    vis[r][c] = N;

    ans = 1;
    for(int i = 0; i < 4; i ++) {
        int vr = r + step[0][i], vc = c + step[1][i];
        if(inside(vr, vc) && downward(r, c, vr, vc)) {
            ans = max(ans, dp(vr, vc) + 1);
        }
    }
    return ans;
}

int main() {
    memset(vis, -1, sizeof(vis));
    scanf("%d", &N);
    while(N--) {
        scanf("%s%d%d", name, &R, &C);
        for(int i = 0; i < R; i ++) {
            for(int j = 0; j < C; j ++) {
                scanf("%d", &G[i][j]);
            }
        }

        int ans = 0;
        for(int i = 0; i < R; i ++) {
            for(int j = 0; j < C; j ++) {
                if(vis[i][j] != N)
                    ans = max(ans, dp(i, j));
            }
        }
        printf("%s: %d\n", name, ans);
    }
    return 0;
}