Leetcode - Wall and Gates
Tags: Bread First Search, LeetCodeYou are given a m x n 2D grid initialized with these three possible values.
-
-1 - A wall or an obstacle.
-
0 - A gate.
-
INF - Infinity means an empty room. We use the value 231 - 1 = 2147483647 to represent INF as you may assume that the distance to a gate is less than 2147483647. Fill each empty room with the distance to its nearest gate. If it is impossible to reach a gate, it should be filled with INF.
For example, given the 2D grid:
|
1 2 3 4 |
INF -1 0 INF INF INF INF -1 INF -1 INF -1 0 -1 INF INF |
After running your function, the 2D grid should be:
|
1 2 3 4 |
3 -1 0 1 2 2 1 -1 1 -1 2 -1 0 -1 3 4 |
Analysis
The standard solution to search the shortest path in a unweighted graph is to use the bread first search algorithm (BFS).
We can start from each gate, and use BFS to calculate the shortest length for each empty room that can be reachable from the gate. Since a room may be reachable from different gates, when the current shortest path from a gate is less than the shortest path from a previous gate, we update the value.
Please Note:
- To prevent duplicated visits, we should not visit the gates in the path, as each gate will be traversed as the root.
- In bread first search, we need to track the visited node to prevent unnecessary duplicated visits.
- Since a room can not be reachable through a wall, the wall node should not put into the queue.
The following is the Java Implementation:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 |
import java.util.HashSet; import java.util.LinkedList; import java.util.Queue; import java.util.Set; public class WallAndGates { public void wallsAndGates(int[][] rooms) { if(rooms.length == 0) return; for(int row = 0; row < rooms.length; row++){ for(int col = 0; col < rooms[0].length; col++){ //if the current node is door, use BFS to calculate // the shortest path for each room that can be reachable // from this door if(rooms[row][col] == 0) bfs(rooms, row, col); } } } class Cell { Integer row; Integer col; int level; Cell(int row, int col, int level) { this.row = row; this.col = col; this.level = level; } @Override public int hashCode() { return row.hashCode() + col.hashCode(); } @Override public boolean equals(Object obj) { Cell other = (Cell)obj; return this.row == other.row && this.col == other.col; } } // for each door, we calculate the shortest path from the door to the reachable room // we update the room with the shortest distance from this door void bfs(int[][] rooms, int row, int col) { // rooms[row][col] must be 0 if(rooms[row][col] != 0) return; Queue<Cell> q = new LinkedList<>(); Set<Cell> visited = new HashSet<>(); Cell curCell = new Cell(row, col, 0); q.add(curCell); int dis = 0; int[] colMove = {-1, +1, 0, 0}; int[] rowMove = {0, 0, -1, +1}; while(!q.isEmpty()){ Cell cur = q.poll(); visited.add(cur); int nextDis = cur.level + 1; int curRow = cur.row; int curCol = cur.col; // move left, right, down and up for(int i = 0; i <= 3; i++ ){ int nextRow = curRow + rowMove[i]; int nextCol = curCol + colMove[i]; // check the whether next cell is valid if(nextRow >= 0 && nextRow < rooms.length && nextCol >= 0 && nextCol < rooms[0].length) { // check whether the next cell is room if(rooms[nextRow][nextCol] != 0 && rooms[nextRow][nextCol] != -1) { rooms[nextRow][nextCol] = Math.min(rooms[nextRow][nextCol], nextDis); Cell nextNode = new Cell(nextRow, nextCol, nextDis); // if the next cell has been visited, don't put it into the queue if(!visited.contains(nextNode)){ q.add(nextNode); } } } } } } public static void main(String[] args) { int INF = Integer.MAX_VALUE; int[][] rooms = {{INF, -1, 0, INF}, {INF, INF, INF, -1}, {INF, -1, INF, -1}, {0, -1, INF, INF}}; new WallAndGates().wallsAndGates(rooms); for(int row = 0; row < rooms.length; row++){ for(int col = 0; col < rooms[0].length; col++){ System.out.print(rooms[row][col] + " "); } System.out.println(" "); } } } |
The output:
3 -1 0 1
2 2 1 -1
1 -1 2 -1
0 -1 3 4
Please leave a comment if you have any questions or want to share a better solution.
Reference:
https://segmentfault.com/a/1190000003906674
https://discuss.leetcode.com/category/358/walls-and-gates
