dfs纯爆搜

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

const int N = 305;
const int INF = 0x3f3f3f3f;
int r, c;
int arr[N][N];
int x[4] = {0,0,1,-1}, y[4] = {1,-1,0,0};
int st[N][N];
int res = -INF;

void dfs(int dx, int dy, int step){
    memset(st,0,sizeof(st));
    if(step > res){
        res = step;
        //return;
    }
    for(int i = 0; i < 4; i++){
        int nx = dx + x[i], ny = dy + y[i];
        if(nx < 0 || nx >= r || ny < 0 || ny >= c || st[nx][ny]) continue;
        if(arr[nx][ny] >= arr[dx][dy]) continue;
        st[nx][ny] = 1;
        dfs(nx, ny, step + 1);
        st[nx][ny] = 0;
    } 
}

int main(){ 
    scanf("%d%d", &r, &c);
    for(int i = 0; i < r; i++){
        for(int j = 0; j < c; j++){
            scanf("%d", &arr[i][j]);
        }
    }
    for(int i = 0; i < r; i++){
        for(int j = 0; j < c; j++){
            dfs(i, j, 1);
        }
    }
    cout << res << endl;
    return 0;
}

dfs+记忆化搜索

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

const int N = 305;
const int INF = 0x3f3f3f3f;
int r, c;
int arr[N][N];
int x[4] = {0,0,1,-1}, y[4] = {1,-1,0,0};
int f[N][N];
int res = -INF;

int dfs(int dx, int dy){
    if(f[dx][dy]) return f[dx][dy];
    for(int i = 0; i < 4; i++){
        int nx = dx + x[i], ny = dy + y[i];
        if(nx < 0 || nx >= r || ny < 0 || ny >= c) continue;
        if(arr[nx][ny] >= arr[dx][dy]) continue;
        f[dx][dy] = max(f[dx][dy], dfs(nx, ny) + 1);
    } 
    if(!f[dx][dy]) f[dx][dy] = 1;
    return f[dx][dy];
}

int main(){ 
    scanf("%d%d", &r, &c);
    for(int i = 0; i < r; i++){
        for(int j = 0; j < c; j++){
            scanf("%d", &arr[i][j]);
        }
    }
    for(int i = 0; i < r; i++){
        for(int j = 0; j < c; j++){
            res = max(res, dfs(i, j));
        }
    }
    cout << res << endl;
    return 0;
}