UVA-10285-Longest Run on a Snowboard

比眉伴天荒 2021-12-23 11:34 115阅读 0赞

### 链接：https://vjudge.net/problem/UVA-10285 ###

### 题意： ###

给你一个二维矩阵，任意选一个起始点，每次可走上下左右四个方向。

但是只能走比他小的格子，求最长的一条路的长度。

### 思路： ###

dp\[i\]\[j\]表示从i，j位置开始的最长路。

得到转移方程dp\[i\]\[j\] = max(dp\[ti\]\[tj\]) + 1,(ti,tj)表示周围能走的点。

同时dfs记忆化搜索。

### 代码： ###

#include <iostream>
    #include <memory.h>
    #include <vector>
    #include <map>
    #include <algorithm>
    #include <cstdio>
    #include <math.h>
    #include <queue>
    #include <string>
    #include <stack>
    #include <iterator>
    #include <stdlib.h>
    #include <time.h>
    #include <assert.h>
    
    using namespace std;
    typedef long long LL;
    
    const int MAXN = 100 + 10;
    int Next[4][2] = {
         {-1, 0}, {0, 1}, {1, 0}, {0, -1}};
    int Map[MAXN][MAXN];
    int dp[MAXN][MAXN];
    int r, c;
    
    int Dfs(int x, int y)
    {
        if (dp[x][y] != -1)
            return dp[x][y];
        dp[x][y] = 0;
        for (int i = 0;i < 4;i++)
        {
            int tx = x + Next[i][0];
            int ty = y + Next[i][1];
            if (tx < 1 || tx > r || ty < 1 || ty > c)
                continue;
            if (Map[x][y] <= Map[tx][ty])
                continue;
            dp[x][y] = max(dp[x][y], Dfs(tx ,ty));
        }
        return ++dp[x][y];
    }
    
    int main()
    {
        int t;
        cin >> t;
        while (t--)
        {
            string name;
            cin >> name >> r >> c;
            for (int i = 1;i <= r;i++)
                for (int j = 1;j <= c;j++)
                    cin >> Map[i][j];
            memset(dp, -1, sizeof(dp));
            int res = -1;
            for (int i = 1;i <= r;i++)
            {
                for (int j = 1;j <= c;j++)
                    res = max(res, Dfs(i, j));
            }
            cout << name << ": " << res << endl;
        }
    
        return 0;
    }

转载于:https://www.cnblogs.com/YDDDD/p/10664462.html