GrowingPain.java

// http://ccs.adnu.edu.ph/acm-icpc2010/prob06_growing_pain.pdf

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

public class GrowingPain {
    
    public static void main(String[] args) throws IOException {
        (new GrowingPain()).run();
    }
    
    public void run() throws IOException {
        BufferedReader br = new BufferedReader(new FileReader("prob06.in"));
        
        String input;
        int caseNum = 1;
        while (null != (input = br.readLine())) {
            String[] parts = input.split(":");
            String[] nums = parts[1].trim().split(" ");
            int cIndex = 0;
            
            GrowingPainCase c = new GrowingPainCase();
            
            int m = Integer.parseInt(nums[cIndex++]);
            int n = Integer.parseInt(nums[cIndex++]);
            
            c.m = m;
            c.n = n;
            
            c.matrix = new Cell[m][n];
            c.cellLookup = new HashMap<Integer, Cell>();
            int cellNum = 1;
            
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    Cell cell = new Cell();
                    cell.CellNumber = cellNum;
                    c.matrix[i][j] = cell;
                    c.cellLookup.put(cellNum, cell);
                    
                    cellNum++;
                }
            }
            
            //c.print();
            //System.out.println();
            
            for (; cIndex < nums.length; cIndex++) {
                int grownCellRef = Integer.parseInt(nums[cIndex]);
                Cell grownCell = c.cellLookup.get(grownCellRef);
                grownCell.Grown = true;
                grownCell.Group = grownCell.CellNumber;
                grownCell.IsSourceCell = true;
            }
            
            c.identifyObjects();
            
            do {
                //c.print();
                //System.out.println();
                c.grow();
            } while (!c.withOverlaps());
            
            //c.print();
            
            System.out.print("Case " + caseNum++ + ": ");
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    Cell x = c.matrix[i][j];
                    if (x.Overlapped) {
                        System.out.print(x.CellNumber + " ");
                    }
                }
            }
            System.out.println();
        }
    }
    
    private class GrowingPainCase {
        public Cell[][] matrix;
        public int m;
        public int n;
        public HashMap<Integer, Cell> cellLookup;
        
        private int growthStep = 1;
        
        public void grow() {
            clearFlags();
            
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    Cell currentCell = matrix[i][j];
                    
                    if (currentCell.IsSourceCell) {
                        int iMinus = i - growthStep;
                        int iPlus = i + growthStep;
                        int jMinus = j - growthStep;
                        int jPlus = j + growthStep;
                        
                        for (int i2 = iMinus; i2 <= iPlus; i2++) {
                            for (int j2 = jMinus; j2 <= jPlus; j2++) {
                                if (!(i2 == i && j2 == j) && i2 >= 0 && i2 < m && j2 >= 0 && j2 < n) {
                                    growCell(i2, j2, currentCell.Group);
                                }
                            }
                        }
                    }
                }
            }
            
            growthStep++;
        }
        
        public boolean withOverlaps() {
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (matrix[i][j].Overlapped)
                        return true;
                }
            }
            return false;
        }
        
        public void growCell(int i, int j, int growthGroup) {
            Cell cell = matrix[i][j];
            
            if (cell.Overlapped) {
            }
            else if (cell.Grown) {
                if (cell.Group != growthGroup) {
                    cell.Overlapped = true;
                    cell.GrowthFlag = true;
                }
            }
            else {
                cell.Grown = true;
                cell.Group = growthGroup;
                cell.GrowthFlag = true;
            }
        }
        
        public void clearFlags() {
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    matrix[i][j].GrowthFlag = false;
                }
            }
        }
        
        public void identifyObjects() {            
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    Cell currentCell = matrix[i][j];
                    
                    if (currentCell.Grown) {
                        if (i != m - 1) {
                            group(currentCell, matrix[i + 1][j]);
                            if (j != n - 1) {
                                group(currentCell, matrix[i + 1][j + 1]);
                            }
                        }
                        if (j != n - 1) {
                            group(currentCell, matrix[i][j + 1]);
                        }
                    }
                }
            }
        }
        
        public void group(Cell cell1, Cell cell2) {
            if (cell2.Grown) {
                reassignGroup(cell2.Group, cell1.Group);
            }
        }
        
        public void reassignGroup(int originalGroupNumber, int newGroupNumber) {
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    Cell currentCell = matrix[i][j];
                    if (currentCell.Group == originalGroupNumber) {
                        currentCell.Group = newGroupNumber;
                    }
                }
            }
        }
        
        public void print() {
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    Cell cell = matrix[i][j];
                    if (cell.Overlapped)
                        System.out.print(" [");
                    else if (cell.Grown)
                        System.out.print(" (");
                    else
                        System.out.print("  ");
                    System.out.format("%2d", cell.CellNumber);
                    System.out.print(":");
                    System.out.format("%2d", cell.Group);
                    if (cell.Overlapped)
                        System.out.print("] ");
                    else if (cell.Grown)
                        System.out.print(") ");
                    else
                        System.out.print("  ");
                }
                System.out.println();
            }
        }
    }
    
    private class Cell {
        public int CellNumber;
        public int Group;
        public boolean GrowthFlag;
        public boolean Grown;
        public boolean IsSourceCell;
        
        public boolean Overlapped;
    }
}