(UVA) You want what filled? - Solution 2

For this solution, I used Breadth-First Search.

If you want to see another solution using Depth-First Search, click here.


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

class Main  {
    public static char[][] m;
    public static char[][] addedToQueue;
    public static int count;
   
    public static void bfs(int i, int j, int rows, int cols) {
        Queue<Coord> queue = new ArrayDeque<Coord>();
        Coord c = new Coord(i, j);
        queue.add(c);
        addedToQueue[i][j] = 1;
       
        int[] vi = {-1,1,0,0};
        int[] vj = {0,0,-1,1};
       
        while (queue.size() > 0) {
            Coord currCoord = queue.poll();
            int currI = currCoord.i;
            int currJ = currCoord.j;
            count++;
           
            for (int k = 0; k < 4; k++) {
                int nextI = currI+vi[k];
                int nextJ = currJ+vj[k];
                if (nextI >= 0 && nextI < rows && nextJ >= 0 && nextJ < cols && addedToQueue[nextI][nextJ] == 0 && m[nextI][nextJ] == m[i][j]) {
                    c = new Coord(nextI, nextJ);
                    queue.add(c);
                    addedToQueue[nextI][nextJ] = 1;
                }
            }    
        }
    }
   
    public static void checkHoles(int rows, int cols, ArrayList<Holes> list) {
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (m[i][j] != '.' && addedToQueue[i][j] == 0) {
                    count = 0;
                    bfs(i, j, rows, cols);
                    list.add(new Holes(m[i][j], count));
                }
            }
        }
    }
   
    public static void readMatrix(BufferedReader br, int rows, int cols) throws NumberFormatException, IOException {
        for (int i = 0; i < rows; i++) {
            String line = br.readLine();
            for (int j = 0; j < cols; j++) {
                m[i][j] = line.charAt(j);
            }
        }
    }
   
    public static void process() throws NumberFormatException, IOException {   
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
       
        int numCase = 0;
        StringTokenizer st = new StringTokenizer(br.readLine());
        int rows = Integer.parseInt(st.nextToken());
        int cols = Integer.parseInt(st.nextToken());
       
        while (rows != 0 || cols != 0) {
            m = new char[rows][cols];
            readMatrix(br, rows, cols);
           
            addedToQueue = new char[rows][cols];
            ArrayList<Holes> list = new ArrayList<Holes>();
            checkHoles(rows, cols, list);
           
            Collections.sort(list);
           
            System.out.println("Problem " + ++numCase + ":");
            for (int i = 0; i < list.size(); i++) {
                System.out.println(list.get(i).letter + " " + list.get(i).qty);
            }
           
            st = new StringTokenizer(br.readLine());
            rows = Integer.parseInt(st.nextToken());
            cols = Integer.parseInt(st.nextToken());
        }
                       
        return;
    }
   
    public static void main(String[] args) throws NumberFormatException, IOException {
        Main m = new Main();
        m.process();

        System.exit(0);
    }
}

class Coord {
    int i;
    int j;
   
    public Coord(int i, int j) {
        this.i = i;
        this.j = j;
    }
}

class Holes implements Comparable<Holes>{
    char letter;
    int qty;
   
    public Holes(char letter, int qty) {
        this.letter = letter;
        this.qty = qty;
    }
   
    public int compareTo(Holes hole) {
        int compareQty = hole.qty;
       
        if (this.qty == compareQty) {
            char compareLetter = hole.letter;
           
            return this.letter - compareLetter;
        }
        else {
            return compareQty - this.qty;
        }
    }
}