P - FatMouse and Cheese HDU - 1078——dfs+记忆化搜索

柔情只为你懂 2022-06-10 03:59 169阅读 0赞

Think:  
1知识点：dfs+记忆化搜索  
2题意：输入一个邻接矩阵，求一条递增路径，满足沿四个方向直线移动最多k步的条件，使得路径经过的点权之和最大

[vjudge题目链接][vjudge]

以下为Accepted代码

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    
    using namespace std;
    
    const int inf = 0x3f3f3f3f;
    const int N = 114;
    
    int n, k, vis[N][N], e[N][N];
    int jk[4][2] = {
       {
       0,1},{
       1,0},{
       0,-1},{-1,0}};
    
    bool Judge(int dx, int dy);
    int dfs(int x, int y);/*dfs+记忆化搜索*/
    
    int main(){
        while(scanf("%d %d", &n, &k) && (n != -1 || k != -1)){
            for(int i = 1; i <= n; i++){
                for(int j = 1; j <= n; j++){
                    scanf("%d", &e[i][j]);
                }
            }
            memset(vis, 0, sizeof(vis));/*记忆化数组初始化*/
            printf("%d\n", dfs(1, 1));
        }
        return 0;
    }
    bool Judge(int dx, int dy){
        if(dx < 1 || dx > n || dy < 1 || dy > n)
            return false;
        else
            return true;
    }
    int dfs(int x, int y){
        if(vis[x][y])/*记忆化搜索*/
            return vis[x][y];
        int ans = 0;
        for(int i = 1; i <= k ; i++){
            for(int j = 0; j < 4; j++){
                int dx = x + jk[j][0]*i;
                int dy = y + jk[j][1]*i;
                if(Judge(dx, dy) && e[x][y] < e[dx][dy])
                    ans = max(ans, dfs(dx, dy));/*通过递归回溯实现逆向更新最优解*/
            }
        }
        vis[x][y] = ans + e[x][y];
        return vis[x][y];
    }

[vjudge]: https://vjudge.net/contest/163018#problem/P