【打卡】牛客网:BM61 矩阵最长递增路径

2023-12-14 09:46:37

技巧:

1.dfs中,虽然num不需要变化,但是在调用函数时加上&,可以防止超时。

2. 一种快速创建NxM维、元素都为0的vector的方法:

????????vector<vector<int>> dp(n, vector <int> (m));

自己写的:

递归的方法

class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 递增路径的最大长度
     * @param matrix int整型vector<vector<>> 描述矩阵的每个数
     * @return int整型
     */

    void dfs(int i, int j, int n, int m, vector<vector<int>> &num, int cur, int& res) {

        //下
        if (i + 1 < n && num[i + 1][j] > num[i][j])
            dfs(i + 1, j, n, m, num, cur + 1, res);
        //上
        if (i - 1 >= 0 && num[i - 1][j] > num[i][j])
            dfs(i - 1, j, n, m, num, cur + 1, res);
        //左
        if (j - 1 >= 0 && num[i][j - 1] > num[i][j])
            dfs(i, j - 1, n, m, num, cur + 1, res);
        //右
        if (j + 1 < m && num[i][j + 1] > num[i][j])
            dfs(i, j + 1, n, m, num, cur + 1, res);

        res = res > cur ? res : cur;
        return;
    }

    int solve(vector<vector<int> >& matrix) {
        // write code here
        int n = matrix.size();
        int m = matrix[0].size();
        int res_all = -1;

        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++) {
                int res = -1;
                dfs(i, j, n, m, matrix, 1, res);
                res_all = res_all > res ? res_all : res;
            }

        return res_all;
    }
};

模板的:

class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 递增路径的最大长度
     * @param matrix int整型vector<vector<>> 描述矩阵的每个数
     * @return int整型
     */

    int n;
    int m;
    int dirs[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};
    int dfs(int i, int j, vector<vector<int>> &num, vector<vector<int>> & dp) {
        if(dp[i][j]!=0) //是与简单粗暴的递归不同的关键,即不需要再次计算该点往其他方向前进的步数了。
            return dp[i][j];
        
        dp[i][j]++; //该点是0的话,开始处理:自己一定是1。
        
        for(int k = 0; k < 4; k++){
            int nexti = i + dirs[k][0];
            int nextj = j + dirs[k][1];

            if(nexti >= 0 && nexti < n && nextj >= 0 && nextj < m && num[nexti][nextj] > num[i][j])
                dp[i][j] = max(dp[i][j], dfs(nexti, nextj, num, dp)+1);
        }

        return dp[i][j]; //最后一次递归,一定是最开始进入的点(的步数)
    }

    int solve(vector<vector<int> >& matrix) {
        // write code here
        if(matrix.size() == 0 || matrix[0].size() == 0)
            return 0;
            
        int res_all = 0;
        n = matrix.size();
        m = matrix[0].size();

        vector<vector<int>> dp(n, vector <int> (m));

        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++) {
                res_all = max(res_all, dfs(i, j, matrix, dp));
            }

        return res_all;
    }
};

文章来源:https://blog.csdn.net/weixin_47173826/article/details/134731508
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。