LeetCode刷题--- 黄金矿工

设计代码

（1）全局变量

int ret;
bool visit[16][16];
int dx[4] = { 0, 0, -1, 1 };
int dy[4] = { 1, -1, 0, 0 };

• ret（最大的值）
• visit（二位数组中的元素是否被用过）
• dx[4]（用于计算）
• dy[4]（用于计算）

（2）设计递归函数

void dfs(vector<vector<int>>& grid, int x, int y, int path);

• 参数：x（当前需要进?处理的元素横坐标），y（当前需要进?处理的元素横坐标），path（当前已经处理的元素值得和）；
• 返回值：无?；
• 函数作用：判断当前坐标的元素作为字符串中下标的元素出现时，向四个?向传递，查找最大值

递归过程

1. 遍历每个位置，标记当前位置并将当前位置的数字作为?字?进?递归，并且在回溯时撤回标记。
   1. 在每个递归的状态中，我们维护?个步数 path，表?当前已经处理了数字的和·。
   2. 若下一个的数字为0，则不向下递归。
2. 对当前位置的上下左右四个相邻位置进?递归，找出最大的路径值。

代码实现

• 时间复杂度：爆搜复杂度为指数级别，分析时空复杂度意义不大
• 空间复杂度：爆搜复杂度为指数级别，分析时空复杂度意义不大

class Solution {
public:
int ret;
bool visit[16][16];
int dx[4] = { 0, 0, -1, 1 };
int dy[4] = { 1, -1, 0, 0 };

    void dfs(vector<vector<int>>& grid, int x, int y, int path)
    {
        ret = max(ret, path);

        int m = grid.size();
        int n = grid[0].size();

        for (int i = 0; i < 4; i++)
        {
            int x1 = x + dx[i], y1 = y + dy[i];
            if (x1 >= 0 && x1 < m && y1 >= 0 && y1 < n &&!visit[x1][y1] && grid[x1][y1] != 0)
            {
                visit[x1][y1] = true;
                dfs(grid, x1, y1, path + grid[x1][y1]);
                visit[x1][y1] = false;
            }
        }
    }

    int getMaximumGold(vector<vector<int>>& grid) 
    {
        for (int i = 0; i < grid.size(); i++)
        {
            for (int j = 0; j < grid[i].size(); j++)
            {
                if (grid[i][j] != 0)
                {
                    visit[i][j] = true;
                    dfs(grid, i, j, grid[i][j]);
                    visit[i][j] = false;
                }
            }
        }

        return ret;
    }
};