You are in charge of preparing a recently purchased lot for one of Amazon's new buildings. The lot is covered with trenches and has a single obstacle that needs to be taken down before the foundation can be prepared for the building. The demolition robot must remove the obstacle before progress can be made on the building. Write an algorithm to determine the minimum distance required for the demolition robot to remove the obstacle.
Assumptions:
• The lot is flat, except for trenches, and can be represented as a two-dimensional grid.
• The demolition robot must start from the top-left corner of the lot, which is always flat, and can move one block up, down, left, or right at a time.
• The demolition robot cannot enter trenches and cannot leave the lot.
• The flat areas are represented as 1, areas with trenches are represented by 0 and the obstacle is represented by 9.
Input
The input to the function/method consists of three arguments:
numRows, an integer representing the number of rows;
numColumns, an integer representing the number of columns;
lot, representing the two-dimensional grid of integers.
Output
Return an integer representing the minimum distance traversed to remove the obstacle else return -1.
Constraints
1 <= numRows, numColumns <=1000
Example
Input:
numRows= 3
numColumns = 3
lot= [ [1, 0, 0],
[1, 0, 0],
[1, 9, 1]]
Output:
3
题意：
在一个matrix中， 1 代表有路，0代表没路，9代表目的地。从左上角出发，求达到目的地9的最短距离。如果到达不了，返回-1。
注意几个边界条件：这题隐藏了一个条件就是机器人从左上角的(0,0)坐标出发，意味着(0,0) 坐标对应的值一定为1，否则直接无解返回-1。但有一个坑，如果出发点为9，则需return 0
思路：
BFS
复杂度分析：
Time: O(numRows * numColumns)
我需要走完matrix的每个position
Space: O(numRows * numColumns)
我需要将matrix中的每个position的信息存入 matrix[][]
代码
1 import java.util.LinkedList; 2 import java.util.*; 3 import java.util.Queue; 4 5 public class RemoveObstacle { 6 int removeObstacle(int numRows, int numColumns, List<List<Integer>> lot){ 7 int[][] matrix = new int[numRows][numColumns]; 8 boolean[][]visited = new boolean[numRows][numColumns]; 9 int result = 0; 10 int[][]dirs = new int[][]{{1,0}, {-1,0}, {0,1}, {0,-1}}; 11 Queue<int[]> queue = new LinkedList<>(); 12 // Robot starts from top-left {0,0} 13 queue.offer(new int[]{0,0}); 14 15 /* 16 PART1: convert List<List<Integer>> lot -> matrix 2D grid 17 */ 18 for (int i = 0; i < lot.size() ; i++) { 19 List<Integer> sub = lot.get(i); 20 for (int j = 0; j < sub.size() ; j++) { 21 matrix[i][j] = lot.get(i).get(j); 22 } 23 } 24 25 /* 26 PART2: bfs 27 */ 28 while(!queue.isEmpty()){ 29 int size = queue.size(); 30 for (int i = 0; i < size; i++) { 31 int[] curr = queue.poll(); 32 int x = curr[0]; 33 int y = curr[1]; 34 if( x < 0 || y < 0 || x >=numRows || y >=numColumns || matrix[x][y] == 0 || visited[x][y]){ 35 continue; 36 } 37 visited[x][y] = true; 38 if(matrix[x][y] == 9 ){ 39 return result; 40 } 41 for(int[] dir : dirs){ 42 int x_ = dir[0] + x; 43 int y_ = dir[1] + y; 44 queue.offer(new int[]{x_, y_}); 45 } 46 } 47 result++; 48 } 49 return -1; 50 } 51 52 /* 53 TEST CASE 54 */ 55 public static void main(String[] args) { 56 List<Integer> list1 = new ArrayList<>(); 57 list1.add(1); 58 list1.add(0); 59 list1.add(0); 60 List<Integer> list2 = new ArrayList<>(); 61 list2.add(1); 62 list2.add(0); 63 list2.add(0); 64 List<Integer> list3 = new ArrayList<>(); 65 list3.add(1); 66 list3.add(9); 67 list3.add(1); 68 List<List<Integer>> lot = new ArrayList<>(); 69 lot.add(list1); 70 lot.add(list2); 71 lot.add(list3); 72 for (int i = 0; i < lot.size(); i++) { 73 System.out.println(lot.get(i).get(0) + "," + lot.get(i).get(1) + "," + lot.get(i).get(2)); 74 } 75 RemoveObstacle test = new RemoveObstacle(); 76 int numRows = 3; 77 int numColumns = 3; 78 System.out.println(test.removeObstacle(numRows, numColumns, lot)); 79 } 80 }转载于:https://www.cnblogs.com/liuliu5151/p/11020672.html
相关资源：Multiple Obstacle Detection and Tracking using Stereo Vision