“This is the 19th time I have participated in the 2022 First Revision Challenge. For more details: 2022 First Revision Challenge”

1219. Gold miner

You want to develop a gold mine, and geological surveyors have mapped the distribution of resources in the gold mine and mapped it in m by N grids. The integers in each cell represent the amount of gold in that cell; If the cell is empty, it is 0.

To maximize their returns, miners need to mine gold according to the following rules:

Every time a miner enters a cell, all the gold in that cell is collected. The miner can walk in four directions at a time from his current position. Each cell can only be mined once. A cell with 0 gold shall not be mined. Miners can start or stop at any cell in the grid that contains gold.

Example 1:

Input: the grid = [,6,0 [0], [5,8,7], [0,9,0]] output: 24 explanation: [,6,0 [0], [5,8,7], [0,9,0]] a collect gold route is: most 9 – > 8 – > 7.

Example 2:

Input: the grid = [,0,7 [1], [2,0,6], [three, four, five], [0,3,0], [9,0,20]] output: 28 explanation: ,0,6,0,7 [[1], [2], [three, four, five], [0,3,0], [9,0,20]] a most gold line is: 1 – > 2 – > 3 – > 4 – > 5 – > 6 – > 7.

 

Tip:

1 <= grid. Length, grid[I]. Length <= 15 0 <= grid[I][j].

Analysis of the

First of all, let’s understand if we go, that is, if represents up, down, left, right, middle, four directions. If we are on line [2,2], we go up to [2,1], go down to [2,3], go left to [1,2], and go left to [2,1].

Then each step we take will light the current mine (the current gold count is set to 0). In addition, we cannot enter the mine where gold is 0, which means that under normal circumstances, we can’t go back to the mine where gold is 0, and we can’t go back to the mine where gold is 0, and it ends when we can’t go back to the mine where gold is 0.

We go through all the scenarios and we find the route that collects the most gold.

Gradually achieve

Define dirS to store the calculated data when we analyzed the up, down, left, and right walks.

const dirs = [[0, -1], [0.1], [...1.0], [1.0]
Copy the code

Define ans to hold the gold we collect

const ans = 0
Copy the code

The two layers represent the starting points of all our paths, and of course the golden number of starting points cannot be zero.

for (let i = 0; i < m; ++i) {
    for (let j = 0; j < n; ++j) {
        if(grid[i][j] ! = =0) {
            dfs(i,j,0)}}}Copy the code

At each step, the current gold number is collected and compared to the maximum number. When it is greater than the maximum number, the maximum number is replaced.

const dfs = (x, y, gold) = > {
    gold = gold + grid[x][y];
    ans = Math.max(ans, gold);
}
Copy the code

Record the current location and set the gold number for the current location to 0.

const dfs = (x, y, gold, dirs) = > {
    gold = gold + grid[x][y];
    ans = Math.max(ans, gold);
    const rec = grid[x][y];
    grid[x][y] = 0;
}

Copy the code

To explore the four directions of the current position, of course, we need to pay attention to the boundary value and the gold number can not be 0. It’s a deeply recursive process. And when we get to the point where we have no other way to go we go back to where we are so that we can find all the paths and find the one that collects the most gold out of all the paths.

const dfs = (x, y, gold, dirs) = > {
    gold = gold + grid[x][y];
    ans = Math.max(ans, gold);
    const rec = grid[x][y];
    grid[x][y] = 0;
    for (let d = 0; d < 4; ++d) {
        const nx = x + dirs[d][0];
        const ny = y + dirs[d][1];
       if (nx >= 0 && nx < m && ny >= 0 && ny < n && grid[nx][ny] > 0) {
            dfs(nx, ny, gold);
       }
    }
    grid[x][y] = rec;
}

Copy the code

The complete code

/ * * *@param {number[][]} grid
 * @return {number}* /
var getMaximumGold = function(grid) {
    const m = grid.length;
    const n = grid[0].length;
    const dirs = [[0, -1], [0.1], [...1.0], [1.0]].let ans = 0;

    const dfs = (x, y, gold) = > {
        gold = gold + grid[x][y];
        ans = Math.max(ans, gold);

        const rec = grid[x][y];
        grid[x][y] = 0;

        for (let d = 0; d < 4; ++d) {
            const nx = x + dirs[d][0];
            const ny = y + dirs[d][1];
            if (nx >= 0 && nx < m && ny >= 0 && ny < n && grid[nx][ny] > 0) {
                dfs(nx, ny, gold);
            }
        }

        grid[x][y] = rec;
    }
    for (let i = 0; i < m; ++i) {
        for (let j = 0; j < n; ++j) {
            if(grid[i][j] ! = =0) {
                dfs(i, j, 0); }}}return ans;
};
Copy the code