Re: [閒聊] 每日leetcode已回收
※ 引述 《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
→
05/14 13:05,
1年前
, 1F
05/14 13:05, 1F
→
05/14 13:05,
1年前
, 2F
05/14 13:05, 2F
→
05/14 13:05,
1年前
, 3F
05/14 13:05, 3F
推
05/14 13:15,
1年前
, 4F
05/14 13:15, 4F
推
05/14 13:21,
1年前
, 5F
05/14 13:21, 5F
→
05/14 14:04,
1年前
, 6F
05/14 14:04, 6F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 218 之 1554 篇)：