Path with Maximum Gold（C++黄金矿工）

亦凉 2022-11-06 06:48 10阅读 0赞

解题思路：

（1）递归求解

class Solution {
    public:
        void helper(vector<int> vis,vector<vector<int>>& grid,vector<int> &v,vector<vector<int>> &d,
                    int x,int y,int m,int n,int temp) {
            temp += grid[x][y];
            vis[x*n+y] = 1;
            
            for(int i=0;i<d.size();i++) {
                if(0<=x+d[i][0] && x+d[i][0]<m && 0<=y+d[i][1] && y+d[i][1]<n && 
                   vis[(x+d[i][0])*n+y+d[i][1]]==0 && grid[x+d[i][0]][y+d[i][1]]!=0) {
                    helper(vis,grid,v,d,x+d[i][0],y+d[i][1],m,n,temp);
                } else v.push_back(temp);
            }
        }
        
        int getMaximumGold(vector<vector<int>>& grid) {
            int m = grid.size(),n=grid[0].size();
            vector<int> v;
            vector<int> vis(m*n,0);
            vector<vector<int>> d={
       {1,0},{-1,0},{0,1},{0,-1}};
            for(int i=0;i<m;i++) {
                for(int j=0;j<n;j++) {
                    if(grid[i][j]!=0) {
                        vis.assign(m*n,0);
                        int temp = 0;
                        helper(vis,grid,v,d,i,j,m,n,temp);
                    }
                }
            }
            
            auto max_index = max_element(v.begin(),v.end());
            return v[max_index-v.begin()];
        }
    };

发表评论取消回复

表情：

评论列表（有 0 条评论，10人围观）

还没有评论，来说两句吧...

相关阅读

相关你的记忆里有黄金矿工吗？

黄金矿工是大概是我初中时候玩的游戏吧，记忆中的样子是一群人围在一个电脑傍边，两人一组，输了就换下一组，虽然它不上现在游戏的丰富的游戏内容。但是就是让人欲罢不能，成为一款经典！

喜欢ヅ旅行/ 2023年10月02日 18:39/ 0 赞/ 8 阅读

相关 unity黄金矿工

文章目录一、介绍二、知识点三、四、碰撞检测五、游戏控制器六、动画七、下载工程文件 ---------

刺骨的言语ヽ痛彻心扉/ 2023年09月26日 21:49/ 0 赞/ 124 阅读

相关【hard】124. Binary Tree Maximum Path Sum

Given a non-empty binary tree, find the maximum path sum. For this problem, a path is d

清疚/ 2023年08月17日 17:20/ 0 赞/ 46 阅读

相关【NewCode-LeetCode】binary-tree-maximum-path-sum

题目：[传送门][Link 1] 题意：问题就类似于在一个无向图中，以某个点为起点，以另一个点为终点，使其从起点到终点的路劲和最大，而这里就是把无向图变成了二叉树

﹏ヽ暗。殇╰゛Y/ 2023年02月22日 13:47/ 0 赞/ 22 阅读

相关 Path with Maximum Gold（C++黄金矿工）

解题思路：（1）递归求解 class Solution { public: void helper(vector<int> vis,vec

亦凉/ 2022年11月06日 06:48/ 0 赞/ 11 阅读

相关 LeetCode124—Binary Tree Maximum Path Sum

LeetCode124—Binary Tree Maximum Path Sum 原题 > Given a binary tree, find the maximu

Love The Way You Lie/ 2022年08月21日 10:59/ 0 赞/ 25 阅读

相关 Binary Tree Maximum Path Sum--LeetCode

题目： Given a binary tree, find the maximum path sum. The path may start and end at an

忘是亡心i/ 2022年08月07日 12:38/ 0 赞/ 30 阅读

相关 leetcode 124. Binary Tree Maximum Path Sum

Given a binary tree, find the maximum path sum. For this problem, a path is defined as

谁践踏了优雅/ 2022年07月26日 12:23/ 0 赞/ 152 阅读

相关 LeetCode-124：Binary Tree Maximum Path Sum

题目 ![70][] 很高兴leetcode上点击量最高的解法和我一样，而且这题难度也就Medium吧我真是提交了n多遍才理解了这题什么意思：在二叉树中，

迷南。/ 2022年05月15日 08:08/ 0 赞/ 131 阅读

相关 Binary Tree Maximum Path Sum

Given a binary tree, find the maximum path sum. For this problem, a path is defined as

迷南。/ 2021年12月17日 10:35/ 0 赞/ 194 阅读