※ 引述 《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;
}
};