BFS Java with explanation


  • 0
    N
    1. find the gate first
    2. use BFS to find INF, no need to consider 0, -1, or other numbers
    class Pair{
        int x;
        int y;
        public Pair(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
    
    public class Solution {
        int[] dir = {0, 1, 0, -1, 0};
        
        final int NUM = 4;
        
        public void wallsAndGates(int[][] rooms) {
            Queue<Integer> steps = new LinkedList<Integer>();
            Queue<Pair> queue = new LinkedList<Pair>();
            
            
            if (rooms == null || rooms.length == 0 || rooms[0].length == 0) {
                return;
            }
            
            for (int i = 0; i < rooms.length; i++) {
                for (int j = 0; j < rooms[0].length; j++) {
                    if (rooms[i][j] == 0) {
                        Pair gate = new Pair(i, j);
                        queue.offer(gate);
                        steps.offer(0);
                    }
                }
            }
            
            while (!queue.isEmpty()) {
                Pair cur = queue.poll();
                int step = steps.poll();
                
                for (int i = 0; i < NUM; i++) {
                    int row = cur.x + dir[i];
                    int col = cur.y + dir[i + 1];
                    
                    if (row < 0 || row >= rooms.length || col < 0 || col >= rooms[0].length) {
                        continue;
                    }
                    
                    if (rooms[row][col] == Integer.MAX_VALUE) {
                        rooms[row][col] = step + 1;
                        Pair next = new Pair(row, col);
                        queue.offer(next);
                        steps.offer(step + 1);
                    }
                    
                    else {
                        continue;
                    }
                }
            }
            
        }
    }

  • 0
    Y
    This post is deleted!

  • 0
    N

    @yixuanwang.start Yep, that is the advantage of BFS, first come first serve. Btw, you also can try int[][] directions = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}}; if you like


  • 0
    Y
    This post is deleted!

Log in to reply
 

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