Buttercola: Leetcode: Walls and Gates

Buttercola: Leetcode: Walls and Gates

Wednesday, September 30, 2015 Leetcode: Walls and Gates You are given a m x n 2D grid initialized with these three possible values. -1 0 231 - 1 = 2147483647 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: 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: 3 -1 0 1 2 2 1 -1 1 -1 2 -1 0 -1 3 4 Understand the problem: It is very classic backtracking problem. We can start from each gate (0 point), and searching for its neighbors. We can either use DFS or BFS solution. A DFS Solution: public class Solution { public void wallsAndGates(int[][] rooms) { if (rooms == null || rooms.length == 0) { return; } int m = rooms.length; int n = rooms[0].length; boolean[][] visited = new boolean[m][n]; for (int i = 0; i < m;

Read full article from Buttercola: Leetcode: Walls and Gates