JAVA BFS, easy to understand and read


  • 0
    H

    public class Solution {
    public void wallsAndGates(int[][] rooms) {

        //Algo thinking: revser thinking, from gate to room; BFS
        //time = O(N*M), space = O(N*M)
        
        if (rooms == null || rooms.length == 0) return;
        
        int n = rooms.length;
        int m = rooms[0].length;
        
        int wall = -1, gate = 0, room = Integer.MAX_VALUE;
        
        // step1: find all gates
        Queue<int[]> queue = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (rooms[i][j] == gate) {
                    queue.add(new int[]{i, j});
                }
            }
        }
        
        
        // step2: BFS
        int[][] dir = new int[][]{{1, 0},{-1, 0},{0, 1},{0, -1}};
        while (!queue.isEmpty()) {
            int[] cell = queue.poll();
            for (int[] d: dir) {
                int i = cell[0] + d[0];
                int j = cell[1] + d[1];
                if (i < 0 || j < 0 || i >= n || j >= m || rooms[i][j] != room) continue;
                
                rooms[i][j] = rooms[cell[0]][cell[1]] + 1;
                queue.offer(new int[]{i, j});
            }
        }
        
    }
    

    }


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.