In this lab, you’ll play with the Disjoint Sets data structure and solve a cool problem with it. Hopefully you’ll gain a better understanding of Disjoint Sets and the ways you can use them!
Alice and Bob are strolling somewhere in a high cloudy place, where sticky
bubbles are hanging from the ceiling. Your assignment is to complete the
BubbleGrid class in order to help them figure out how many bubbles will drop
as they pop them.
Bubbles are stored in a 2-D array of 1’s and 0’s. A 1 indicates there is a bubble at that position in the grid, and a 0 indicates there is a space. A bubble will fall if is not “stuck.”
A bubble is stuck if
- It is in the topmost row of the grid, or
- It is orthogonally adjacent to a bubble that is stuck.
Alice and Bob decide to throw a sequence of darts. If a dart hits a bubble, it pops, possibly causing some bubbles to fall. If it hits an empty space, nothing happens.
BubbleGrid instance is bound to a single grid, which is passed in
through its constructor; you may assume this grid is valid (i.e. no
floating unstuck bubbles). You must implement the method
int popBubbles(int darts), such that
dartsis an array of 2-element arrays representing the grid positions (in
[row, column]format) at which darts are thrown in sequence (i.e. a dart is thrown at position
t). You may assume all elements of
dartsare unique, valid positions within the grid.
- It returns an array where the
i-th element is the number of bubbles that fall after the
i-th dart is thrown (popped bubbles do not fall!).
You will probably want to use a union-find data structure to solve this problem.
We’ve given you the Lab 6
UnionFind.java, in case you’d like to implement it yourself, but
feel free to simply use Princeton’s
edu.princeton.cs.algs4.WeightedQuickUnionUF) instead. You may use it as-is or
create a modified version by extending it in
UnionFind.java. Note that your
UnionFind API doesn’t have to match the skeleton’s: you may add/remove methods
as you see fit. We will grade you based on your
Extra Challenge: There are a few ways of solving this problem; can you solve it using only one union-find instance?
[[1, 1, 0], [1, 0, 0], [1, 1, 0], [1, 1, 1]]
[[2, 2], [2, 0]]
popBubbles() should return
This lab was derived from a problem originally found on Leetcode, contributed by Alex Wice.