LeetCode: Robot Move with Obstacles

/**
This was asked in online test of amazon. Very tricky.

A 2-d grid is given with the following cell values:
1- the cells where the robot can move
0 - the niches where the robot cannot move
9 - the cell where an object is located which is to be removed by the cleaning robot.

The robot should start to move from the top left corner and can travel on left, right, top, and bottom. Find the minimum distance the robot can move to remove the object.
Example:
[
[1, 0, 0],
[1, 0, 0],
[1, 9, 1]
]
in the above grid, the robot can start from the top-left corner and travel on (0,0), (1,0), and (2,0) to reach the object, so the minimum distance is 3.
*/
import java.util.*;

public class RobotMoveWithObstacles{

public static int findMinDist(List<List<Integer>> lot, int rows, int cols){
//base case
if(lot==null){
return -1;
}
int dist = dfs(lot, rows, cols, 0, 0, 0);
return dist;
}

public static int dfs(List<List<Integer>> lot, int rows, int cols, int x, int y, int dist){
if(x<0 || y<0 || x>=rows || y>=cols || lot.get(x).get(y)==0){
return Integer.MAX_VALUE;
}
if(lot.get(x).get(y)==9){
return dist;
}
lot.get(x).set(y, 0);
//left
int left = dfs(lot, rows, cols, x-1, y, dist+1);
//right
int right = dfs(lot, rows, cols, x+1, y, dist+1);
//top
int top = dfs(lot, rows, cols, x, y-1, dist+1);
//bottom
int bottom = dfs(lot, rows, cols, x, y+1, dist+1);
dist = Math.min(Math.min(left, right), Math.min(top, bottom));
return dist;
}

public static void main(String[] args){
List<List<Integer>> lot = new ArrayList<List<Integer>>();
int rows = 3, cols = 3;
lot.add(new ArrayList<Integer>());
lot.add(new ArrayList<Integer>());
lot.add(new ArrayList<Integer>());
lot.get(0).add(1);
lot.get(0).add(0);
lot.get(0).add(0);
lot.get(1).add(1);
lot.get(1).add(0);
lot.get(1).add(0);
lot.get(2).add(1);
lot.get(2).add(9);
lot.get(2).add(1);
int dist = findMinDist(lot, rows, cols);
System.out.println("dist is:"+dist);
}
}

No comments:

Post a Comment