algorithms/Percolation/Percolation.java at master · rafaelnec/algorithms · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
/******************************************************************************
 *  Name:    Rafael Neves Moraes
 *
 *  Description:  Percolation system using an n-by-n grid of sites.
 *
 *  Written:       8/05/2019
 *
 *  % javac-algs4 Percolation.java
 *  % java-algs4 Percolation <file>
 *
 *  Formatter:
 *      <file> :
 *          n -> number of lines
 *          row col -> list of rows and cols
 *          Ex.:
 *               20
 *                 7  11
 *                18  11
 *                12   5
 *                 9   5
 *                 5   9
 ******************************************************************************/
import edu.princeton.cs.algs4.WeightedQuickUnionUF;
import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.Stopwatch;

public class Percolation {

    private final WeightedQuickUnionUF wqu, wqd;
    private final int nt; // Number of elements
    private int os; // Number of open sites
    private boolean[] op; // Is Open?
    private boolean p; // Is Percolate?
    private int tc; // Top component


    // create n-by-n grid, with all sites blocked
    public Percolation(int n) {
        if (n <= 0)
            throw new IllegalArgumentException("N must be gran than 0!");

        wqu = new WeightedQuickUnionUF(n * n + 1);
        wqd = new WeightedQuickUnionUF(n * n + 1);
        op  = new boolean[n * n];
        os  = 0;
        nt  = n;
        p   = false;
        tc  = 0;

    }

    // open site (row, col) if it is not open already
    public void open(int row, int col) {

        this.validateRowCol(row, col);

        int idx = getIndex(row, col);
        int idxWqu = getIndexWqu(row, col);

        if (!op[idx]) {

            os += 1;
            op[idx] = true;

            if (row == 1)
                wqu.union(0, idxWqu);

            if (row == nt)
                wqd.union(0, idxWqu);

            if (col > 1 && op[idx - 1])
                union(idxWqu, idxWqu - 1);
            if (col < nt && op[idx + 1])
                union(idxWqu, idxWqu + 1);
            if (row > 1 && op[idx - nt])
                union(idxWqu, idxWqu - nt);
            if (row < nt && op[idx + nt])
                union(idxWqu, idxWqu + nt);

            if (!p && wqd.connected(0, idxWqu) && wqu.connected(0, idxWqu))
                p = true;

            tc = wqu.find(0);

        }

    }

    private void union(int x, int y) {
        wqu.union(x, y);
        wqd.union(x, y);
    }

    // is site (row, col) open?
    public boolean isOpen(int row, int col) {
        this.validateRowCol(row, col);
        return op[getIndex(row, col)];
    }

    // is site (row, col) full?
    public boolean isFull(int row, int col) {
        this.validateRowCol(row, col);
        return wqu.find(getIndexWqu(row, col)) == tc;
    }

    // number of open sites
    public int numberOfOpenSites() {
        return os;
    }

    // does the system percolate?
    public boolean percolates() {
        return p;
    }

    // validate row and col
    private void validateRowCol(int row, int col) {
        if (row <= 0 || row > nt)
            throw new IllegalArgumentException("row value " + row + " out of bounds!");
        if (col <= 0 || col > nt)
            throw new IllegalArgumentException("col value " + col + " out of bounds!");
    }

    // get row index
    private int getIndex(int row, int col) {
        return (nt * (row - 1)) + col - 1;
    }

    // get row index
    private int getIndexWqu(int row, int col) {
        return (nt * (row - 1)) + col;
    }

    // test client (optional)
    public static void main(String[] args) {

        Stopwatch sw = new Stopwatch();

        In in = new In(args[0]);      // input file
        int n = in.readInt();         // n-by-n percolation system

        // repeatedly read in sites to open and draw resulting system
        Percolation perc = new Percolation(n);
        while (!in.isEmpty()) {
            int i = in.readInt();
            int j = in.readInt();
            perc.open(i, j);
        }

        System.out.println(String.format("number of open sites: %s", perc.numberOfOpenSites()));
        System.out.println(String.format("is percolates: %s", perc.percolates()));
        System.out.println(String.format("Running time: %ss", sw.elapsedTime()));

    }

}