(UVA) The die is cast - Solution

I used Depth-First Search to solve this problem.

After reading the matrix, I use a DFS to find all the characters 'X'. In this method, each group of 'X' receives a number, which will help get the answer in the end. Then, I mark all the '.' position as visited. And finally, I call the DFS method to find all the characters 'X' in every die.

Once each group of 'X' has its own "identification number", I only need to add each ID that I found during the DFS in a structure, and then, count how many different IDs I got. PS.: For every die, it will execute the DFS method once.


import java.io.*;
import java.util.*;

class Main  {
    public static char[][] matrix;
    public static int[][] matrixInt;
    public static boolean[][] visited;
    public static int numRows;
    public static int numCols;
    public static int count;
    public static int[] vx = {-1,0,0,1};
    public static int[] vy = {0,-1,1,0};
    public static HashSet<Integer> added;
   
    public static void dfs(int currX, int currY) {
        if (currX < 0 || currY < 0 || currX >= numRows || currY >= numCols || visited[currX][currY]) {
            return;
        }
        if (matrix[currX][currY] == 'X') {
            added.add(matrixInt[currX][currY]);
        }
        visited[currX][currY] = true;
        for (int i = 0; i < 4; i++) {
            int nextX = currX+vx[i];
            int nextY = currY+vy[i];
            dfs(nextX, nextY);
        }
    }
   
    public static void dfsX(int currX, int currY) {
        if (currX < 0 || currY < 0 || currX >= numRows || currY >= numCols || matrix[currX][currY] != 'X' || visited[currX][currY]) {
            return;
        }
       
        matrixInt[currX][currY] = count;
        visited[currX][currY] = true;
        for (int i = 0; i < 4; i++) {
            int nextX = currX+vx[i];
            int nextY = currY+vy[i];
            dfsX(nextX, nextY);
        }
    }   
   
    public static void process() throws NumberFormatException, IOException {  
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
       
        int numCase = 0;
        String line = br.readLine();
        String[] s = line.split("\\s");
        numRows = Integer.parseInt(s[1]);
        numCols = Integer.parseInt(s[0]);
        while (numRows != 0 || numCols != 0) {
            matrix = new char[numRows][numCols];
            for (int i = 0; i < numRows; i++) {
                line = br.readLine();
                for (int j = 0; j < numCols; j++) {
                    matrix[i][j] = line.charAt(j);
                }
            }

            count = 0;
            matrixInt = new int[numRows][numCols];
            visited = new boolean[numRows][numCols];
            for (int i = 0; i < numRows; i++) {
                for (int j = 0; j < numCols; j++) {
                    if (matrix[i][j] == 'X' && !visited[i][j]) {
                        dfsX(i, j); // number all 'X'
                        count++;
                    }
                }
            }
           
            visited = new boolean[numRows][numCols];
            for (int i = 0; i < numRows; i++) {
                for (int j = 0; j < numCols; j++) {
                    if (matrix[i][j] == '.') {
                        visited[i][j] = true;
                    }
                }
            }
           
            ArrayList<Integer> dice = new ArrayList<Integer>();
            for (int i = 0; i < numRows; i++) {
                for (int j = 0; j < numCols; j++) {
                    if (!visited[i][j]) {
                        added = new HashSet<Integer>();
                        dfs(i, j);
                        dice.add(added.size());
                    }
                }
            }
           
            Collections.sort(dice);
           
            System.out.println("Throw " + ++numCase);
            if (dice.size() == 0) {
                System.out.println("0\n");
            }
            else {
                for (int i = 0; i < dice.size()-1; i++) {
                    System.out.print(dice.get(i) + " ");
                }
                System.out.println(dice.get(dice.size()-1) + "\n");
            }
           
            line = br.readLine();
            s = line.split("\\s");
            numRows = Integer.parseInt(s[1]);
            numCols = Integer.parseInt(s[0]);           
        }
                       
        return;
    }
  
    public static void main(String[] args) throws NumberFormatException, IOException {
        Main m = new Main();
        m.process();

        System.exit(0);
    }
}