Re: [閒聊] 每日leetcode

[oinishere (是oin捏)]

※ 引述 《Rushia (早瀬ユウカの体操服)》 之銘言：
: 　
: https://leetcode.com/problems/path-with-maximum-gold/description
: 1219. Path with Maximum Gold
: 給你一個二維陣列grid表示金礦的座標，grid[i][j] 表示該位置有多少金礦，你可以
: 從任意位置當起點開始挖金礦，滿足以下條件：
: 1.每次都要挖完當前位置的金礦
: 2.你可以往上下左右移動
: 3.你不可以移動到沒金礦的位置
: 求出最多可以挖多少金礦
: 　
: 思路：
: 1.從每個金礦座標開始窮舉所有挖金礦的可能，用回朔法標記已經挖過的金礦，取最大
:   的即可。
: 　
: 




思路:

反正全部dfs一定可以

所以就先搞一個dfs的東西

然後每次不同起點都找

然後經過的地方就標記

要注意的就是

退回去的時候要改回標記的數值

這樣就可以利用同一個pass過的陣列了

就 比較省記憶體

不過

我好像

速度跟空間都超爛欸

速度beat 30% memory beat 44%

我吐了


class Solution {
public:

    vector<vector<bool>> pass;
    int ma ;

    void walk(vector<vector<int>>& grid , int i , int j , int now )
    {

        if(i<0 || i==grid.size() || j<0 || j==grid[0].size())return;
        if(grid[i][j] == 0)return;
        if(pass[i][j] == 1)return;

        pass[i][j] = 1;

        now += grid[i][j];


        ma = max(now , ma);


        walk(grid,i-1,j,now);
        walk(grid,i,j-1,now);
        walk(grid,i+1,j,now);
        walk(grid,i,j+1,now);


        pass[i][j] = 0;
    };

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

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

        ma = 0;
        pass.resize(n,vector<bool>(m,0));

        for(int i = 0 ; i < n ; i ++)
        {
            for(int j = 0 ; j < m ; j ++)
            {
                walk(grid,i,j,0);
            }
        }

        return ma;
    }
};




--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 61.230.142.93 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1715663083.A.F71.html
→ SecondRun: 多提交幾次
→ SecondRun: 都沒有提升代表你真的爛
→ oinishere: 多提交幾次 變20% 我哭了
推 wu10200512: 你怎麼不打週賽
推 JIWP: 大師
→ Rushia: 不用pass吧 直接改grid回溯就好