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