## Adobe Interview Question

SDE1s**Country:**India

if I understood this then,

here 1 means blocked

and 2/0 means gold with values 2/0

You need the shortest path with max gold count

it simply dfs/bfs problem I think

```
set<int> paths_sum;
int r,c;
bool isSafe(int sx,int sy,vector<vector<int>> &grid){
if(sx<0 || sy<0 || sx>=r || sy>=c || grid[sx][sy]==1)return 0;
return 1;
}
void dfs(int sx,int sy,int dx,int dy,vector<vector<int>> &grid,int sum){
if(sx<0 || sy<0 || sx>=r || sy>=c || grid[sx][sy]==1)return;
if(sx==dx && sy==dy){paths_sum.insert(sum); sum=0; }
int temp= grid[sx][sy];
grid[sx][sy]=1;
if(isSafe(sx+1,sy,grid)) dfs(sx+1,sy,dx,dy,grid,sum+grid[sx+1][sy]);
if(isSafe(sx,sy+1,grid)) dfs(sx,sy+1,dx,dy,grid,sum+grid[sx][sy+1]);
if(isSafe(sx,sy-1,grid)) dfs(sx,sy-1,dx,dy,grid,sum+grid[sx][sy-1]);
if(isSafe(sx-1,sy,grid)) dfs(sx-1,sy,dx,dy,grid,sum+grid[sx-1][sy]);
grid[sx][sy]=temp;
}
int min_path(int n,int m,int dx,int dy,vector<vector<int>> grid){
r=n;
c=m;
paths_sum.clear();
dfs(0,0,dx,dy,grid,0);
if(paths_sum.size()<1) return -1;
return *paths_sum.end();
}
```

Also there can be DP solution

You need the shortest path with max gold count

it simply dfs/bfs problem I think

```
set<int> paths_sum;
int r,c;
bool isSafe(int sx,int sy,vector<vector<int>> &grid){
if(sx<0 || sy<0 || sx>=r || sy>=c || grid[sx][sy]==1)return 0;
return 1;
}
void dfs(int sx,int sy,int dx,int dy,vector<vector<int>> &grid,int sum){
if(sx<0 || sy<0 || sx>=r || sy>=c || grid[sx][sy]==1)return;
if(sx==dx && sy==dy){paths_sum.insert(sum); sum=0; }
int temp= grid[sx][sy];
grid[sx][sy]=1;
if(isSafe(sx+1,sy,grid)) dfs(sx+1,sy,dx,dy,grid,sum+grid[sx+1][sy]);
if(isSafe(sx,sy+1,grid)) dfs(sx,sy+1,dx,dy,grid,sum+grid[sx][sy+1]);
if(isSafe(sx,sy-1,grid)) dfs(sx,sy-1,dx,dy,grid,sum+grid[sx][sy-1]);
if(isSafe(sx-1,sy,grid)) dfs(sx-1,sy,dx,dy,grid,sum+grid[sx-1][sy]);
grid[sx][sy]=temp;
}
int min_path(int n,int m,int dx,int dy,vector<vector<int>> grid){
r=n;
c=m;
paths_sum.clear();
dfs(0,0,dx,dy,grid,0);
if(paths_sum.size()<1) return -1;
return *paths_sum.end();
}
```

Also there can be DP solution

if I understood this then,

- Shubham Kumar Gupta September 10, 2020here 1 means blocked

and 2/0 means gold with values 2/0

You need the shortest path with max gold count

it simply dfs/bfs problem I think

set<int> paths_sum;

int r,c;

bool isSafe(int sx,int sy,vector<vector<int>> &grid){

if(sx<0 || sy<0 || sx>=r || sy>=c || grid[sx][sy]==1)return 0;

return 1;

}

void dfs(int sx,int sy,int dx,int dy,vector<vector<int>> &grid,int sum){

if(sx<0 || sy<0 || sx>=r || sy>=c || grid[sx][sy]==1)return;

if(sx==dx && sy==dy){paths_sum.insert(sum); sum=0; }

int temp= grid[sx][sy];

grid[sx][sy]=1;

if(isSafe(sx+1,sy,grid)) dfs(sx+1,sy,dx,dy,grid,sum+grid[sx+1][sy]);

if(isSafe(sx,sy+1,grid)) dfs(sx,sy+1,dx,dy,grid,sum+grid[sx][sy+1]);

if(isSafe(sx,sy-1,grid)) dfs(sx,sy-1,dx,dy,grid,sum+grid[sx][sy-1]);

if(isSafe(sx-1,sy,grid)) dfs(sx-1,sy,dx,dy,grid,sum+grid[sx-1][sy]);

grid[sx][sy]=temp;

}

int min_path(int n,int m,int dx,int dy,vector<vector<int>> grid){

r=n;

c=m;

paths_sum.clear();

dfs(0,0,dx,dy,grid,0);

if(paths_sum.size()<1) return -1;

return *paths_sum.end();

}

Also there can be DP solution