/* cashcow.java Cash Cow, 2013 Mid-Central Programming Competition, Problem G Java Solution by Andy Harrington For the collapse, lists are more convenient than arrays. I convert the coordinate to usual list indices starting at 0. The region clicked on could be marked by changing the character, but that requires an extra step if the region is too small. I use the alternative of remembering the SET of points in the region. They need to be remembered and sorted, and that is not built in for ordered pairs in java, so when remembering the region, I linearize to integers, like with memory in a 2D array. Higher points have larger codes, so it is important to remove points in reverse order to keep later lower indices unchanged. */ import java.util.*; import java.io.*; public class cashcow { static int WIDE = 10, HIGH = 12; static ArrayList> grid; static HashSet codes; public static void main(String[] args) throws Exception { String file = (args.length > 0) ? args[0] : "cashcow.in"; Scanner in = new Scanner(new File(file)); int N = in.nextInt(); while (N != 0) { grid = new ArrayList>(); for (int x = 0; x < WIDE; x++) grid.add(new ArrayList()); for (int y = 0; y < HIGH; y++) { String row = in.next(); for (int x = 0; x < WIDE; x++) grid.get(x).add(0, row.charAt(x)); } for (int i = 0; i < N; i++) click(in.next().charAt(0) - 'a', in.nextInt()-1); // x, y int tot = 0; for (List col: grid) tot += col.size(); System.out.println(tot); N = in.nextInt(); } } static void click(int x0, int y0) { // click at x0,y0; reduce grid char c = getCh(x0, y0); if (c == ' ') return; // nothing there codes = new HashSet(); // remember region, coded as int's expand(x0, y0, c); // find whole region; list in codes if (codes.size() < 3) return; Integer[] ca = codes.toArray(new Integer[0]); // need array for Arrays.sort(ca); // built-in sort for (int i = ca.length-1; i >= 0; i--) // reversed so higher out 1st grid.get(ca[i] % WIDE).remove(ca[i] / WIDE); // collapse columns for (int x = grid.size()-1; x >= 0; x--) // reversed so higher out 1st if (grid.get(x).size() == 0) // collapse rows grid.remove(x); } static char getCh(int x, int y) { if (x < 0 || x >= grid.size() || y < 0 || y >= grid.get(x).size()) return ' '; return grid.get(x).get(y); } static void expand(int x, int y, char c) {//if c at (x,y): include, spread int code = WIDE*y + x; // standard linearization of 2D if (getCh(x, y) != c || codes.contains(code)) return; codes.add(code); expand(x+1, y, c); expand(x-1, y, c); expand(x, y+1, c); expand(x, y-1, c); } }