Amazon Interview Question Developer Program Engineers
Since, S will always be (0,0) and F will always be (N,M). we can use A* algorithm.
Follow the connected components i.e. 1s but when two possible paths are given chose the one closest to F using A* heuristic
initially the mice is at (0,0) we push the unvisited neighbours of it into the queue(also the neighbour should not be blocked) and we note that they are at distance 1 unit from the source(0,0). Now we remove one element from the queue and push all its neighbours which havent been pushed into the queue earlier into the queue and note that they are at distance 2 units from source. We keep on doing this until we reach the final position or until the queue becomes empty. if the queue becomes empty it means that we cannot reach the destination at all.
This is the code for the rough idea.
int minDistance(const vector<vector<int> > &Input){
int m = Input.size();
int n = Input[0].size();
queue<int> x,y,L;
vector<vector<bool> > visit(m,vector<bool>(n,0));
x.push(0),y.push(0),L.push(0);
visit[0][0]=1;
static int dx[]={-1,0,1,0};
/*if diagonal movement is allowed u need to add 4 more values*/
static int dy[]={0,-1,0,1};
while(!x.empty()){
int a=x.front(),b=y.front(),l=L.front();
x.pop(),y.pop(),L.pop();
if(a==m-1 && b==n-1){
cout<<"Destionation is reachable"<<endl;
return l;//l is the minimum distance.
}
for(int i=0;i<4;i++){
int t1 = a+dx[i],t2=b+dy[i],m=l+1;
if(t1>=0 && t1<m && t2>=0 && t2<n && !visit[t1][t2] && Input[t1][t2]){
x.push(t1),y.push(t2),L.push(m),visit[t1][t2]=1;
visit[t1][t2]=1;
}
}
}
return -1;//queue is empty, so path is not found
}
I don;t the question is correct. Every valid path from source to destination is the shortest path.
I think in order to find the shortest path we will have to look at the available options .. Even in the single source shortest path algorithms any path selected initially to a node might not be the shortest but in the end we find the best path.. So all available paths will be traversed ..
This is wht i feel..
I am really luking fwd to see if someone really has a solution to this ..
Can't this be done recursively? i.e. assume A is the matrix
if (A[n-1][m] == 1) and (A[n][m-1] == 1), then F(N,M) = Min (F(n-1,m), F(n, m-1)) + 1.
if (A[n-1][m] == 0) then F(n,m) = f(n,m-1) + 1.
if (A[n][m-1] == 0) then F(n,m) = f(n-1,m) +1.
if ((A[n][m-1] == 0) && (A[n-1][m] == 0)) then there is no solution.
FIND-PATH(x, y)
if (x,y outside maze) return false
if (x,y is goal) return true
if (x,y not open) return false
mark x,y as part of solution path
if (FIND-PATH(North of x,y) == true) return true
if (FIND-PATH(East of x,y) == true) return true
if (FIND-PATH(South of x,y) == true) return true
if (FIND-PATH(West of x,y) == true) return true
unmark x,y as part of solution path
return false
BFS would be your best options. The maze of actually a graph where '1' are the vertices which have edges connecting other adjacent '1's and 0s do not have any edges connecting other vertices. Now all you have to do is run a BFS on the grid. You can keep a distance array where you can update the solution everytime or you can use a backtrack after finding the shortest path by maintaining a 'previous' array which stores the previous vertex you came from for every vertex. Standard problem .Also, no need to build a graph. There is a standard way to execute BFS in a grid. Just google
I assume the program finds any shortest (or longest) path and then exits.
- jiangok October 31, 2010Define happy move as x++ or y++ and unhappy move as x-- and y--. An happy path consists of all happy moves and a happy path (if exists) is also shortest path. An unhappy path consists of happy moves and unhappy moves.
To find a shortest path, starting from S, on each node, the rat tries to make a happy move as a preference. If the rat is blocked anywhere, backtrack.
To find a longest path, starting from S, on each node, we tries to make an unhappy move as a preference. If the rat is blocked anywhere, backtrack.
This is a greedy algorithm and does not guarantee finding a shortest (or longest) path. Look forward to a better algorithm.