【Link】:

【Description】



在一个r*c的格子上;

求最长的下降路径;

【Solution】



记忆化搜索;

f[x][y]表示从(x,y)这个格子往下还能走多远;

因为是严格递增,所以有单调性.



【NumberOf WA】



0



【Reviw】

【Code】

#include <bits/stdc++.h>

using namespace std;

const int N = 100+10;

const int dx[5] = {0,1,-1,0,0};

const int dy[5] = {0,0,0,1,-1};

const int INF = 0x3f3f3f3f;

int T,r,c,a[N][N],f[N][N];

char s[30];

int dfs(int x,int y){

    if (f[x][y]!=-1) return f[x][y];

    int ma = 0;

    for (int i = 1;i <= 4;i++){

        int tx = x + dx[i],ty = y + dy[i];

        if (tx <1 || tx > r || ty <1 || ty > c) continue;

        if (a[tx][ty]<a[x][y])

            ma = max(ma,dfs(tx,ty));

    }

    return f[x][y] = ma+1;

}

int main(){

    //freopen("F:\\rush.txt","r",stdin);

    scanf("%d",&T);

    while (T--){

        scanf("%s",s+1);

        scanf("%d%d",&r,&c);

        for (int i = 1;i <= r;i++)

            for (int j = 1;j <= c;j++)

                scanf("%d",&a[i][j]);

        memset(f,255,sizeof f);

        int t = dfs(1,1);

        for (int i = 1;i <= r;i++)

            for (int j = 1;j <= c;j++)

                t = max(t,dfs(i,j));

        printf("%s: %d\n",s+1,t);

    }

    return 0;

}