(UVA) You want what filled? - Solution 1

I used Depth-First Search to solve this problem.


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

class Main  {
    public static char[][] m;
    public static char[][] visited;
    public static int count;
   
    public static void dfs(char letter, int i, int j, int rows, int cols) {
        int[] vi = {-1,1,0,0};
        int[] vj = {0,0,-1,1};
       
        if (m[i][j] != letter) {
            return;
        }
        else {
            count++;
            visited[i][j] = 1;
            for (int k = 0; k < 4; k++) {
                int nextI = i+vi[k];
                int nextJ = j+vj[k];
                if (nextI >= 0 && nextI < rows && nextJ >= 0 && nextJ < cols && visited[nextI][nextJ] == 0) {
                    dfs(letter, nextI, nextJ, rows, cols);
                }
            }
        }
    }
   
    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] != '.' && visited[i][j] == 0) {
                    count = 0;
                    dfs(m[i][j], 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);
           
            visited = 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 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;
        }
    }
}

Comments

Popular posts from this blog

(Coderbyte) Powers of Two - Solução

(Coderbyte) Dash Insert II - Solução

(CoderByte) Number Search - Solução