Untitled

mail@pastecode.io avatar
unknown
plain_text
7 months ago
1.3 kB
0
Indexable
Never
class Solution {
public:
    void solve(int x,int y,int &gold,int &maxG,vector<vector<int>>&grid,vector<vector<bool>>&vis,vector<vector<int>>&dir){
        

        vis[x][y]=true;
        int org=grid[x][y];
        gold+=org;
        maxG=max(maxG,gold);
        grid[x][y]=0;

        for(auto d:dir){
            int new_x=x+d[0];
            int new_y=y+d[1];
            if(new_x>=0 && new_x<grid.size() && new_y>=0 && new_y<grid[0].size() && grid[new_x][new_y]!=0 &&!vis[new_x][new_y]){
                
                solve(new_x,new_y,gold,maxG,grid,vis,dir);

        
            }
        }
        grid[x][y]=org;
        gold-=org;
        vis[x][y]=false;
    }

    int getMaximumGold(vector<vector<int>>& grid) {
        int res=0;
        vector<vector<int>>dir ={{-1,0},{1,0},{0,-1},{0,1}};
        vector<vector<bool>>vis(grid.size(),vector<bool>(grid[0].size(),false));
        for(int i=0;i<grid.size();i++){
            for(int j=0;j<grid[0].size();j++){
                int gold=0, maxG=0;
                if(grid[i][j]!=0) {
                    solve(i,j,gold,maxG,grid,vis,dir);
                    res=max(res,maxG);
                }
            }
        }
        return res;
    }
};
Leave a Comment