Java BFS Solution, Easy to understand


  • 0
    W
        public void wallsAndGates(int[][] rooms) {
            if (rooms.length == 0)
                return;
            
            int m = rooms.length;
            int n = rooms[0].length;
            
            int[] vec_x = new int[]{-1, 1, 0, 0};
            int[] vec_y = new int[]{0, 0, -1, 1};
            
            LinkedList<int[]> q = new LinkedList<>();
            
            for (int i=0; i<m; i++)
            {
                for (int j=0; j<n; j++)
                {
                    if (rooms[i][j] == 0)
                    {
                        q.addLast(new int[]{i, j});
                    }
                }
            }
            
            while (!q.isEmpty())
            {
                int[] frontPoint = q.removeFirst();
                for (int i=0;i<4;i++)
                {
                    int tx = frontPoint[0] + vec_x[i];
                    int ty = frontPoint[1] + vec_y[i];
                    
                    if (tx >= 0 && ty >= 0 && tx < m && ty < n && rooms[tx][ty] == Integer.MAX_VALUE)
                    {
                        rooms[tx][ty] = rooms[frontPoint[0]][frontPoint[1]] + 1;
                        q.addLast(new int[]{tx, ty});
                    }
                }
            }
        }
    

Log in to reply
 

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