[C++] 回溯法使用引用传递，lambda 表达式，vector.back() 使用

本文主要是介绍[C++] 回溯法使用引用传递，lambda 表达式，vector.back() 使用，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

1219.黄金矿工
你要开发一座金矿，地质勘测学家已经探明了这座金矿中的资源分布，并用大小为 m * n 的网格 grid 进行了标注。每个单元格中的整数就表示这一单元格中的黄金数量；如果该单元格是空的，那么就是 0。

为了使收益最大化，矿工需要按以下规则来开采黄金：

每当矿工进入一个单元，就会收集该单元格中的所有黄金。
矿工每次可以从当前位置向上下左右四个方向走。
每个单元格只能被开采（进入）一次。
不得开采（进入）黄金数目为 0 的单元格。
矿工可以从网格中任意一个有黄金的单元格出发或者是停止。

示例 1：

输入：grid = [[0,6,0],[5,8,7],[0,9,0]]
输出：24
解释：
[[0,6,0],
[5,8,7],
[0,9,0]]
一种收集最多黄金的路线是：9 -> 8 -> 7。
示例 2：

输入：grid = [[1,0,7],[2,0,6],[3,4,5],[0,3,0],[9,0,20]]
输出：28
解释：
[[1,0,7],
[2,0,6],
[3,4,5],
[0,3,0],
[9,0,20]]
一种收集最多黄金的路线是：1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7。

提示：

1 <= grid.length, grid[i].length <= 15
0 <= grid[i][j] <= 100
最多 25 个单元格中有黄金。

一开始我就是想的递归加回溯
但是我嫌麻烦，就用了值传递

class Solution {
private:
    vector<vector<int>> _grid;

    int getGold(int i, int j, vector<vector<int>> flagCache, int totalGold)
    {
        if(i<0||j<0)
            return totalGold;
        if(i>=_grid.size())
            return totalGold;
        if(j>=_grid[i].size())
            return totalGold;

        if(_grid[i][j] == 0||flagCache[i][j] == 1)
            return totalGold;
        
        flagCache[i][j] = 1;

        vector<int> goldNumCache;

        goldNumCache.push_back(getGold(i-1,j,flagCache,totalGold + _grid[i][j]));
        goldNumCache.push_back(getGold(i+1,j,flagCache,totalGold + _grid[i][j]));
        goldNumCache.push_back(getGold(i,j-1,flagCache,totalGold + _grid[i][j]));
        goldNumCache.push_back(getGold(i,j+1,flagCache,totalGold + _grid[i][j]));
        sort(goldNumCache.begin(),goldNumCache.end());

        return goldNumCache.back();
    }
public:
    int getMaximumGold(vector<vector<int>>& grid) {

        _grid = grid;
        vector<vector<int>> _flag = vector<vector<int>>(grid.size());
        for(int i=0;i<grid.size();i++)
            _flag[i] = vector<int>(grid[i].size());

        vector<int> goldNum;

        for(int i=0;i<grid.size();i++)
        {
            for(int j=0;j<grid[i].size();j++)
            {
                goldNum.push_back(getGold(i,j,_flag,0));
            }
        }

        sort(goldNum.begin(),goldNum.end());
        return goldNum.back();
    }
};

改成引用传递之后我本来还想着在递归调用函数之后回溯的

    int getGold(int i, int j, int totalGold)
    {
        if(i<0||j<0)
            return totalGold;
        if(i>=_grid.size())
            return totalGold;
        if(j>=_grid[i].size())
            return totalGold;

        if(_grid[i][j] == 0||_flag[i][j] == 1)
            return totalGold;
        
        _flag[i][j] = 1;

        vector<int> goldNumCache;

        // 递归
        goldNumCache.push_back(getGold(i-1,j,totalGold + _grid[i][j]));
        // 回溯
        if(goldNumCache.back() != totalGold + _grid[i][j])
            _flag[i-1][j] = 0;
        // 递归
        goldNumCache.push_back(getGold(i+1,j,totalGold + _grid[i][j]));
        // 回溯
        if(goldNumCache.back() != totalGold + _grid[i][j])
            _flag[i+1][j] = 0;
        // 递归
        goldNumCache.push_back(getGold(i,j-1,totalGold + _grid[i][j]));
        // 回溯
        if(goldNumCache.back() != totalGold + _grid[i][j])
            _flag[i][j-1] = 0;
        // 递归
        goldNumCache.push_back(getGold(i,j+1,totalGold + _grid[i][j]));
        // 回溯
        if(goldNumCache.back() != totalGold + _grid[i][j])
            _flag[i][j+1] = 0;
        
        sort(goldNumCache.begin(),goldNumCache.end());

        return goldNumCache.back();
    }

然后这样就错了……
我还在想哪里错了……但是我突然发现其实可以不用想这个了，它本身就麻烦
本来最简单的应该是在返回函数的时候回溯
就，只管自己的状态，这个原则，要遵守
而且确实可以允许这样做，我回溯在递归调用之后就是合理的

    int getGold(int i, int j, int totalGold)
    {
        if(i<0||j<0)
            return totalGold;
        if(i>=_grid.size())
            return totalGold;
        if(j>=_grid[i].size())
            return totalGold;

        if(_grid[i][j] == 0||_flag[i][j] == 1)
            return totalGold;
        
        _flag[i][j] = 1;

        vector<int> goldNumCache;

        // 递归
        goldNumCache.push_back(getGold(i-1,j,totalGold + _grid[i][j]));
        goldNumCache.push_back(getGold(i+1,j,totalGold + _grid[i][j]));
        goldNumCache.push_back(getGold(i,j-1,totalGold + _grid[i][j]));
        goldNumCache.push_back(getGold(i,j+1,totalGold + _grid[i][j]));
        
        sort(goldNumCache.begin(),goldNumCache.end());

        _flag[i][j] = 0;

        return goldNumCache.back();
    }

最终代码：

class Solution {
private:
    vector<vector<int>> _grid;
    vector<vector<int>> _flag;

    int getGold(int i, int j, int totalGold)
    {
        if(i<0||j<0)
            return totalGold;
        if(i>=_grid.size())
            return totalGold;
        if(j>=_grid[i].size())
            return totalGold;

        if(_grid[i][j] == 0||_flag[i][j] == 1)
            return totalGold;
        
        _flag[i][j] = 1;

        vector<int> goldNumCache;

        // 递归
        goldNumCache.push_back(getGold(i-1,j,totalGold + _grid[i][j]));
        goldNumCache.push_back(getGold(i+1,j,totalGold + _grid[i][j]));
        goldNumCache.push_back(getGold(i,j-1,totalGold + _grid[i][j]));
        goldNumCache.push_back(getGold(i,j+1,totalGold + _grid[i][j]));
        
        sort(goldNumCache.begin(),goldNumCache.end());

        _flag[i][j] = 0;

        return goldNumCache.back();
    }
public:
    int getMaximumGold(vector<vector<int>>& grid) {

        _grid = grid;
        _flag = vector<vector<int>>(grid.size());
        for(int i=0;i<grid.size();i++)
            _flag[i] = vector<int>(grid[i].size());

        vector<int> goldNum;

        for(int i=0;i<grid.size();i++)
        {
            for(int j=0;j<grid[i].size();j++)
            {
                goldNum.push_back(getGold(i,j,0));
            }
        }

        sort(goldNum.begin(),goldNum.end());
        return goldNum.back();
    }
};

还是超时了……不懂为啥……
看了一下别人的题解，感觉跟我的一样啊

别人不用 flag，用 grid 置 0 代替，我试试

class Solution {
private:
    vector<vector<int>> _grid;

    int getGold(int i, int j, int totalGold)
    {
        if(i<0||j<0)
            return totalGold;
        if(i>=_grid.size())
            return totalGold;
        if(j>=_grid[i].size())
            return totalGold;

        if(_grid[i][j] == 0)
            return totalGold;
        
        int goldCache = _grid[i][j];
        _grid[i][j] = 0;

        vector<int> goldNumCache;

        // 递归
        goldNumCache.push_back(getGold(i-1,j,totalGold + goldCache));
        goldNumCache.push_back(getGold(i+1,j,totalGold + goldCache));
        goldNumCache.push_back(getGold(i,j-1,totalGold + goldCache));
        goldNumCache.push_back(getGold(i,j+1,totalGold + goldCache));
        
        sort(goldNumCache.begin(),goldNumCache.end());

        _grid[i][j] = goldCache;

        return goldNumCache.back();
    }
public:
    int getMaximumGold(vector<vector<int>>& grid) {

        _grid = grid;

        vector<int> goldNum;

        for(int i=0;i<grid.size();i++)
        {
            for(int j=0;j<grid[i].size();j++)
            {
                goldNum.push_back(getGold(i,j,0));
            }
        }

        sort(goldNum.begin(),goldNum.end());
        return goldNum.back();
    }
};

还是超时了……思考……
让我再看看别人的题解

别人是先判断接下来要走的格子能不能走，然后再调用函数
我是先调用函数然后再判断自己的状态
我记得好像是调用函数也是要耗费时间的，所以才有内联这个东西
再让我试试

class Solution {
private:
    static constexpr int delta[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

public:
    int getMaximumGold(vector<vector<int>>& grid) {

        function<int(int,int,int)> getGold = [&](int x, int y, int totalGold)
        {
            vector<int> totalGoldCache;

            int goldCache = grid[x][y];
            grid[x][y] = 0;

            // 递归
            for(int i=0;i<4;i++)
            {
                int nx = x + delta[i][0];
                int ny = y + delta[i][1];
                if((nx >= 0) && (ny >= 0) && (nx < grid.size()))
                    if(ny < grid[nx].size())
                        if(grid[nx][ny] != 0)
                            totalGoldCache.push_back(getGold(nx, ny, totalGold + goldCache));
            }

            sort(totalGoldCache.begin(), totalGoldCache.end());

            grid[x][y] = goldCache;

            return totalGoldCache.back();
        };

        vector<int> goldNum;

        for(int i=0;i<grid.size();i++)
        {
            for(int j=0;j<grid[i].size();j++)
            {
                if(grid[i][j] != 0)
                    goldNum.push_back(getGold(i,j,0));
            }
        }

        sort(goldNum.begin(),goldNum.end());
        return goldNum.back();
    }
};

这个会出错……因为取 vector 的 back 的时候不一定有值
还需要预先加上一个默认的值

class Solution {
private:
    static constexpr int delta[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

public:
    int getMaximumGold(vector<vector<int>>& grid) {
        
        int m = grid.size(), n = grid[0].size();

        function<int(int,int,int)> getGold = [&](int x, int y, int totalGold)
        {
            vector<int> totalGoldCache;

            int goldCache = grid[x][y];
            grid[x][y] = 0;

            // 递归
            for(int i=0;i<4;i++)
            {
                int nx = x + delta[i][0];
                int ny = y + delta[i][1];
                if (nx >= 0 && nx < m && ny >= 0 && ny < n && grid[nx][ny] > 0)
                    totalGoldCache.push_back(getGold(nx, ny, totalGold + goldCache));
            }

            totalGoldCache.push_back(totalGold + goldCache);
            sort(totalGoldCache.begin(), totalGoldCache.end());

            grid[x][y] = goldCache;

            return totalGoldCache.back();
        };

        vector<int> totalGoldCache2;

        for(int i=0;i<grid.size();i++)
        {
            for(int j=0;j<grid[i].size();j++)
            {
                if(grid[i][j] != 0)
                    totalGoldCache2.push_back(getGold(i,j,0));
            }
        }

        totalGoldCache2.push_back(0);
        sort(totalGoldCache2.begin(),totalGoldCache2.end());
        return totalGoldCache2.back();
    }
};

这样就好了

这篇关于[C++] 回溯法使用引用传递，lambda 表达式，vector.back() 使用的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！

C/C++教程

[C++] 回溯法使用引用传递，lambda 表达式，vector.back() 使用

前端开发

后端开发

移动端开发

数据库

服务器运维

人工智能

区块链

游戏开发

网站运营

大数据/云计算

软件工程

软件/开发工具使用

资讯