-
Notifications
You must be signed in to change notification settings - Fork 3
Percolation
This task can cause difficulties if you think about how to solve the backwash problem, if you do not think about it, then the task is quite trivial.
In fact, all you need is an array that stores the state of the cell (for a start, an array of boolean type will be quite enough) and a union-find structure that is two units larger than the number of cells. This size is needed to initialize hidden nodes, which will show the connection to the top or bottom side and will be called the hidden top node and hidden bottom node, respectively. Further, we simply connect an open cell with an adjacent one, if they are also open. But if it is the top cell or the bottom one, then when they are opened, they must connect to the corresponding hidden cell. This method is simple enough to work with PercolationStats, but nevertheless the isFull () method will have incorrect logic.
It's not very hard to guess that to solve the backwash problem, you can use an additional union-find structure. The first one will be responsible for percolation itself, and the auxiliary one for backwash. Thus, the isFull () method will check if this cell is connected to the top hidden cell in the backwash union-find structure. And the percolates () method will return the same value as in the previous example. The main difference here is how the bottom cells are attached to the hidden bottom cell in the main and auxiliary structure. In the auxiliary, the connection will be carried out if and only if the cell to be connected is already connected to the upper hidden cell.
An efficient backwash solution can be solved with one array of integers and one union-find structure. The bottom line here is that in addition to the state of openness and closedness of the cell, the array stores the value of its connection to the upper or lower hidden cell. Information can be stored in the format of zeros and ones, for example:
grid[4] = 101
where first number is connectivity to top hidden cell (if 1 then connected), middle is connectivity to bottom hidden cell, and the last is a state of cell. Thus, using this solution, you can pass bonus tests in autograder.
There are no difficulties in this class, you perform tests, after each test you write to the threshold in an array, and then, using the methods of the algs4 library, calculate the value that is required by the API.