_286.java

package com.fishercoder.solutions.firstthousand;

import java.util.LinkedList;
import java.util.Queue;

public class _286 {
    public static class Solution1 {

        int[] dirs = new int[] {0, 1, 0, -1, 0};

        public void wallsAndGates(int[][] rooms) {
            if (rooms == null || rooms.length == 0 || rooms[0].length == 0) {
                return;
            }
            int m = rooms.length;
            int n = rooms[0].length;
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (rooms[i][j] == 0) {
                        bfs(rooms, i, j, m, n);
                    }
                }
            }
        }

        void bfs(int[][] rooms, int i, int j, int m, int n) {
            for (int k = 0; k < 4; k++) {
                int x = dirs[k] + i;
                int y = dirs[k + 1] + j;
                if (x >= 0 && y >= 0 && x < m && y < n && rooms[x][y] > rooms[i][j] + 1) {
                    rooms[x][y] = rooms[i][j] + 1;
                    bfs(rooms, x, y, m, n);
                }
            }
        }
    }

    public static class Solution2 {

        // push all gates into the queue first, and then put all its neighbours into the queue with
        // one distance to the gate, then continue to push the rest of the nodes into the queue, and
        // put all their neighbours into the queue with the nodes' value plus one until the queue is
        // empty
        int[] dirs = new int[] {0, 1, 0, -1, 0};

        public void wallsAndGates(int[][] rooms) {
            if (rooms == null || rooms.length == 0 || rooms[0].length == 0) {
                return;
            }
            int m = rooms.length;
            int n = rooms[0].length;
            Queue<int[]> queue = new LinkedList();
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (rooms[i][j] == 0) {
                        queue.offer(new int[] {i, j});
                    }
                }
            }

            while (!queue.isEmpty()) {
                int[] curr = queue.poll();
                for (int k = 0; k < 4; k++) {
                    int x = curr[0] + dirs[k];
                    int y = curr[1] + dirs[k + 1];
                    if (x >= 0 && x < m && y >= 0 && y < n && rooms[x][y] == Integer.MAX_VALUE) {
                        rooms[x][y] = rooms[curr[0]][curr[1]] + 1;
                        queue.offer(new int[] {x, y});
                    }
                }
            }
        }
    }
}