UVa Online Judge Challenge "572"

Published: April 23, 2018 | Last Modified: May 2, 2025

Tags: uva coding challenge disjoint set

Categories: Java

Although BFS and DFS were recommended solutions to the problem, I saw an opportunity to solve this problem using Disjoint Sets. The virtual judge run time was 0.050s.

Problem

My Solution

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        while (true) {
            String[] dimensions = br.readLine().split(" ");
            int rows = Integer.parseInt(dimensions[0]);
            if (rows == 0) {
                System.exit(0);
            }
            int cols = Integer.parseInt(dimensions[1]);
            int size = rows * cols;
            DisjointSet ds = new DisjointSet(size);
            byte[] flattenedGrid = new byte[size];
            /*
            |* This is a 2D grid of characters that I am flattening into a 1D byte 
            |* array. There are only two bytes that I am concerned with: 42 and 64.
            |* 64 represents an oil deposit whereas 42 represent the absence thereof. 
             */
            for (int x = 0; x < rows; x++) {
                System.arraycopy(br.readLine().getBytes(), 0, flattenedGrid, x * cols, cols);
            }
            /*
            |* "Stand" on every position of the grid. If you are standing over
            |* oil, look in every direction around you for an adjacent
            |* oil deposit. Every time oil is spotted adjacent to where you are
            |* standing, union your position and that position into the same set.
             */
            for (int x = 0; x < rows; x++) {
                for (int y = 0; y < cols; y++) {
                    int[] directions = new int[]{-1, -1, -1, -1, -1, -1, -1, -1}; //8 directions
                    int position = x * cols + y;
                    if (flattenedGrid[position] == 64) { //If you are standing on an oil depost
                        if (x > 0) {
                            directions[1] = ((x - 1) * cols) + y;//north
                        }
                        if (y < cols - 1) {
                            directions[2] = ((x - 1) * cols) + y + 1;//north east
                            directions[3] = position + 1;//east
                            directions[4] = ((x + 1) * cols) + y + 1;//south east
                        }
                        if (y > 0) {
                            directions[0] = ((x - 1) * cols) + y - 1;//north west
                            directions[6] = ((x + 1) * cols) + y - 1;//south west
                            directions[7] = position - 1;//west
                        }
                        if (x < rows - 1) {
                            directions[5] = ((x + 1) * cols) + y;//south
                        }
                        /*
                        |* This loop does the actual comparisons and
                        |* if both positions have oil, unions them.
                         */
                        for (int i = 0; i < directions.length; i++) {
                            if (directions[i] >= 0 && directions[i] < size) {
                                if (flattenedGrid[directions[i]] == 64) {
                                    ds.union(position, directions[i]);
                                }
                            }
                        }
                    }
                }
            }
            /*
            |* Now that the algorithm is finished, I count the number of
            |* disjoint sets. This represents the number of distinct oil deposits. 
             */
            int[] counter = new int[size];
            int distinctOilDeposits = 0;
            for (int i = 0; i < size; i++) {
                if (flattenedGrid[i] == 64) {
                    int cursor = ds.find(i);
                    if (counter[cursor] == 0) {
                        distinctOilDeposits++;
                        counter[cursor]++;
                    } else {
                        counter[cursor]++;
                    }
                }
            }
            System.out.println(distinctOilDeposits);
        }
    }
}
class DisjointSet {
    int parent[];
    DisjointSet(int size) {
        parent = new int[size];
        int i;
        for (i = 0; ++i < size;) {
            parent[i] = i;
        }
    }
    int find(int n) {
        return n == parent[n] ? n : find(parent[n]);
    }
    void union(int x, int y) {
        parent[find(x)] = find(y);
    }
}