dfs纯暴力

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

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

void dfs(int dx, int dy, int step){
    memset(st, 0, sizeof(st));
    if(dx <= 0 || dx > r || dy <= 0 || dy > c) return;
    if(step > maxx){
        maxx = step;
    }
    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(num[nx][ny] >= num[dx][dy]) continue;
        st[nx][ny] = 1;
        dfs(nx, ny, step + 1);
        st[nx][ny] = 0;
    }
}

int main(){
    cin >> r >> c;
    for(int i = 1; i <= r; i++){
        for(int j = 1; j <= c; j++){
            cin >> num[i][j];
        }
    }
    for(int i = 1; i <= r; i++){
        for(int j = 1; j <= c; j++){
            dfs(i, j, 1);
        }
    }
    cout << maxx;
    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;
}