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
#include<bits/stdc++.h>
using namespace std;
void def(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
#ifndef ONLINE_JUDGE
freopen("inputz.txt","r",stdin);
freopen("error.txt","r",stderr);
freopen("output.txt","w",stdout);
#endif
}
vector<vector<vector<int>>> dist;
vector<vector<int>> dp;
vector<pair<int,int>> coins;
int R;
int C;
int allOnes, numCoins;
int MAXDIST = 1000 * 1000;
bool isInRange(int r, int c) {
return r >= 0 && r < R && c >= 0 && c < C;
}
void extractCoins(vector<vector<int>> &arr) {
for (int r = 0; r < R; r++)
for (int c = 0; c < C; c++)
if (arr[r][c] == 2)
coins.push_back({r,c});
}
void setDistances(vector<vector<int>> &arr, int coin) {
for (int r = 0; r < R; r++)
for (int c = 0; c < C; c++)
dist[r][c][coin] = MAXDIST;
vector<vector<bool>> visited(R,vector<bool>(C,0));
queue<pair<int,int>> q;
pair<int,int> startPoint = coins[coin];
q.push(startPoint);
visited[startPoint.first][startPoint.second] = 1;
dist[startPoint.first][startPoint.second][coin] = 0;
vector<int> dr = {0, -1, 0, 1};
vector<int> dc = {-1, 0, 1, 0};
while (!q.empty()) {
pair<int,int> point = q.front();q.pop();
int oldR = point.first;
int oldC = point.second;
for (int k = 0; k < 4; k++) {
int newR = oldR + dr[k];
int newC = oldC + dc[k];
if (isInRange(newR, newC) && !visited[newR][newC] && arr[newR][newC] != 1) {
pair<int,int> newPoint = {newR, newC};
visited[newR][newC] = true;
dist[newR][newC][coin] = dist[oldR][oldC][coin] + 1;
q.push(newPoint);
}
}
}
}
int getMinDist(int coin, int seq, int Ra, int Ca) {
if (seq == allOnes) return dist[Ra][Ca][coin];
if (dp[coin][seq] != -1) return dp[coin][seq];
int res = INT_MAX;
for (int i = 0; i < numCoins; i++)
if ((seq & (1 << i)) == 0) {
int newSeq = seq | (1 << i);
pair<int,int> pos = coins[i];
res = min(res, getMinDist(i, newSeq, Ra, Ca) + dist[pos.first][pos.second][coin]);
}
return dp[coin][seq] = res;
}
int minMoves1(vector<vector<int>> &arr, int Ra, int Ca) {
R = arr.size();
C = arr[0].size();
pair<int,int> startPoint = {0, 0};
coins.push_back(startPoint);
extractCoins(arr);
numCoins = coins.size();
allOnes = (1 << numCoins) - 1;
int dpR = numCoins;
int dpC = allOnes + 1;
dp.resize(dpR,vector<int>(dpC,-1));
dist.resize(R,vector<vector<int>>(C,vector<int>(numCoins,0)));
for (int i = 0; i < numCoins; i++)
setDistances(arr, i);
int ans = getMinDist(0, 1, Ra, Ca);
return ans >= MAXDIST ? -1 : ans;
}
int main()
{
def();
int n,m;
cin>>n>>m;
vector<vector<int>> a(n,vector<int>(m,0));
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
cin>>a[i][j];
int dx,dy;
cin>>dx>>dy;
cout<<minMoves1(a,dx,dy);
}
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