P1434 [SHOI2002]滑雪 记忆化dfs c++

1. 主函数中，搜索矩阵的每一个点，从第一个点当做起点开始；每搜完一个点，比较当前的长度ans和dfs(i)得到的结果取最大值；
2. 在dfs中，用两个偏移量dx,dy分别去表示其四个方向，分别去深搜这个x,y点这四个方向，在搜下一个点要满足没访问过以及坡的高度要求，记录当前的点的所能达到的最大长度为max(f[x][y], dfs(xx, yy) + 1)，加上xx,yy这个点，然后继续向下dfs；
3. 需要记忆化搜索，通过一个数组f去记录已经搜过的点所能达到的最大坡度，如果在dfs的开始，发现f[x][y]!=1，说明之前已经搜过这个点，可以直接返回他得值（f数组已经初始化为1了，因为每个点的本身就是一个长度）；

#include "bits/stdc++.h"

using namespace std;
int a[105][105];
int f[105][105];
int n, m;
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};
int vis[105][105];


int dfs(int x, int y) {
    if (f[x][y]!=1)
        return f[x][y];
    for (int k = 0; k < 4; ++k) {
        int xx = x + dx[k];
        int yy = y + dy[k];
        if (xx >= 1 && xx <= n && yy >= 1 && yy <= n && vis[xx][yy] == 0 && a[xx][yy] < a[x][y]) {
            vis[xx][yy] = 1;
            f[x][y] = max(f[x][y], dfs(xx, yy) + 1);
            vis[xx][yy] = 0;
        }
    }
    return f[x][y];
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            cin >> a[i][j];
            f[i][j]=1;
        }
    }
    int ans = 0;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            vis[i][j] = 1;
            ans = max(ans, dfs(i, j));
            vis[i][j] = 0;
        }
    }
    cout << ans;
    return 0;
}