[数据结构与算法]做题笔记--DFS回溯法

class Solution {
public:
int ans=0;
int max(int a,int b){
if( a>b)
return a;
else
return b;
}
void DFS(vector<vector>& grid,int i,int j,int maxi){
int row=grid.size();
int col=grid[0].size();
if(i==-1||j==-1||irow||jcol||grid[i][j]==0){
return;
}
maxi=maxi+grid[i][j];
int mid=grid[i][j];
grid[i][j]=0;
ans=max(ans,maxi);
DFS(grid,i-1,j,maxi);
DFS(grid,i+1,j,maxi);
DFS(grid,i,j-1,maxi);
DFS(grid,i,j+1,maxi);
grid[i][j]=mid;
}
int getMaximumGold(vector<vector>& grid) {
int row=grid.size();
int col=grid[0].size();
for(int i=0;i<row;i++)
for(int j=0;j<col;j++)
DFS(grid,i,j,0);
return ans
;
}
};
注意:保存回溯前的数据，和DFS结束时的条件