文章目录
-
- 原题题目
- 代码实现（首刷自解）
- 代码实现（二刷自解 DAY 252 C++）
原题题目
代码实现（首刷自解）
class Solution {
public:int backtracking(const vector<vector<int>>& grid,vector<vector<bool>>& visit,const vector<vector<int>>& temp,int x,int y){
if(x<0 || x>=grid.size() || y<0 || y>=grid[0].size() || visit[x][y]) return 0;visit[x][y] = true;int ret = grid[x][y];for(int i=0;grid[x][y] && i<4;++i)ret = max(backtracking(grid,visit,temp,x+temp[i][0],y+temp[i][1]) + grid[x][y],ret);visit[x][y] = false;return ret;}int getMaximumGold(vector<vector<int>>& grid) {
vector<vector<bool>> visit(grid.size(),vector<bool>(grid[0].size()));vector<vector<int>> temp{
{
0,1},{
0,-1},{
1,0},{
-1,0}};int ret = 0;for(int x=0;x<grid.size();++x){
for(int y=0;y<grid[0].size();++y)ret = max(backtracking(grid,visit,temp,x,y),ret);}return ret;}
};
代码实现（二刷自解 DAY 252 C++）
class Solution {
public:void depth_first_search(const vector<vector<int>>& grid,vector<vector<bool>>& visit,int x,int y,int& ret,int tmp){
if(x < 0 || x >= grid.size() || y < 0 || y >= grid[0].size() || !grid[x][y] || visit[x][y])return;tmp += grid[x][y];visit[x][y] = true;ret = tmp > ret ? tmp : ret;depth_first_search(grid,visit,x+1,y,ret,tmp);depth_first_search(grid,visit,x-1,y,ret,tmp);depth_first_search(grid,visit,x,y+1,ret,tmp);depth_first_search(grid,visit,x,y-1,ret,tmp);visit[x][y] = false;} int getMaximumGold(vector<vector<int>>& grid) {
vector<vector<bool>> visit(grid.size(),vector<bool>(grid[0].size(),false));int ret = 0;for(int i = 0;i < grid.size();++i){
for(int j = 0;j < grid[0].size();++j){
if(grid[i][j])depth_first_search(grid,visit,i,j,ret,0);}}return ret;}
};