UVa Online Judge Challenge "572"

  1import java.io.BufferedReader;
  2import java.io.IOException;
  3import java.io.InputStreamReader;
  4public class Main {
  5    public static void main(String[] args) throws IOException {
  6        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  7        while (true) {
  8            String[] dimensions = br.readLine().split(" ");
  9            int rows = Integer.parseInt(dimensions[0]);
 10            if (rows == 0) {
 11                System.exit(0);
 12            }
 13            int cols = Integer.parseInt(dimensions[1]);
 14            int size = rows * cols;
 15            DisjointSet ds = new DisjointSet(size);
 16            byte[] flattenedGrid = new byte[size];
 17            /*
 18            |* This is a 2D grid of characters that I am flattening into a 1D byte 
 19            |* array. There are only two bytes that I am concerned with: 42 and 64.
 20            |* 64 represents an oil deposit whereas 42 represent the absence thereof. 
 21             */
 22            for (int x = 0; x < rows; x++) {
 23                System.arraycopy(br.readLine().getBytes(), 0, flattenedGrid, x * cols, cols);
 24            }
 25            /*
 26            |* "Stand" on every position of the grid. If you are standing over
 27            |* oil, look in every direction around you for an adjacent
 28            |* oil deposit. Every time oil is spotted adjacent to where you are
 29            |* standing, union your position and that position into the same set.
 30             */
 31            for (int x = 0; x < rows; x++) {
 32                for (int y = 0; y < cols; y++) {
 33                    int[] directions = new int[]{-1, -1, -1, -1, -1, -1, -1, -1}; //8 directions
 34                    int position = x * cols + y;
 35                    if (flattenedGrid[position] == 64) { //If you are standing on an oil depost
 36                        if (x > 0) {
 37                            directions[1] = ((x - 1) * cols) + y;//north
 38                        }
 39                        if (y < cols - 1) {
 40                            directions[2] = ((x - 1) * cols) + y + 1;//north east
 41                            directions[3] = position + 1;//east
 42                            directions[4] = ((x + 1) * cols) + y + 1;//south east
 43                        }
 44                        if (y > 0) {
 45                            directions[0] = ((x - 1) * cols) + y - 1;//north west
 46                            directions[6] = ((x + 1) * cols) + y - 1;//south west
 47                            directions[7] = position - 1;//west
 48                        }
 49                        if (x < rows - 1) {
 50                            directions[5] = ((x + 1) * cols) + y;//south
 51                        }
 52                        /*
 53                        |* This loop does the actual comparisons and
 54                        |* if both positions have oil, unions them.
 55                         */
 56                        for (int i = 0; i < directions.length; i++) {
 57                            if (directions[i] >= 0 && directions[i] < size) {
 58                                if (flattenedGrid[directions[i]] == 64) {
 59                                    ds.union(position, directions[i]);
 60                                }
 61                            }
 62                        }
 63                    }
 64                }
 65            }
 66            /*
 67            |* Now that the algorithm is finished, I count the number of
 68            |* disjoint sets. This represents the number of distinct oil deposits. 
 69             */
 70            int[] counter = new int[size];
 71            int distinctOilDeposits = 0;
 72            for (int i = 0; i < size; i++) {
 73                if (flattenedGrid[i] == 64) {
 74                    int cursor = ds.find(i);
 75                    if (counter[cursor] == 0) {
 76                        distinctOilDeposits++;
 77                        counter[cursor]++;
 78                    } else {
 79                        counter[cursor]++;
 80                    }
 81                }
 82            }
 83            System.out.println(distinctOilDeposits);
 84        }
 85    }
 86}
 87class DisjointSet {
 88    int parent[];
 89    DisjointSet(int size) {
 90        parent = new int[size];
 91        int i;
 92        for (i = 0; ++i < size;) {
 93            parent[i] = i;
 94        }
 95    }
 96    int find(int n) {
 97        return n == parent[n] ? n : find(parent[n]);
 98    }
 99    void union(int x, int y) {
100        parent[find(x)] = find(y);
101    }
102}