286. Walls and Gates

Walls and Gates

You 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:

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

Solution

public class Solution {
   public void wallsAndGates(int[][] rooms) {
        if (rooms == null || rooms.length == 0) return;
        int row = rooms.length;
        int column = rooms[0].length;

        for (int i = 0; i < row; i++) {
            for (int j = 0; j < column; j++) {
                if (rooms[i][j] == 0) {
                    traverse(rooms, i, j, row, column, 0);
                }
            }
        }
    }

    private void traverse(int[][] rooms, int x, int y, int row, int column, int distance) {
        if (!(x >= 0 && x < row && y >= 0 && y < column)) {
            return;
        }

        if (rooms[x][y] < distance) {
            return;
        }

        rooms[x][y] = distance;
        traverse(rooms, x + 1, y, row, column, distance + 1);
        traverse(rooms, x, y + 1, row, column, distance + 1);
        traverse(rooms, x - 1, y, row, column, distance + 1);
        traverse(rooms, x, y - 1, row, column, distance + 1);
    }

}