// An absolutely abominable solution to "Squadtrees" // Bob Roos // // For an n by n B & W image (n a power of two), this program recursively // constructs a complete degree-four tree while counting the number of // nodes in a quad tree and in a squad tree. In order to correctly // count squad tree nodes, each subtree is "registered" the first // time it appears. After the initial construction and registration // of each tree, all further references to it contribute nothing // more to the node count. import java.io.*; import java.util.*; class Node { // Used for determining blocks of solid color: public String color; // B (leaf), W (leaf), or M (mixed, nonleaf) // pointers to the four children: public Node child[]; public String signature; // "w0 w1 w2 w3" // where wi = indexOf(signature(child[i]) // in the tree registry // Special leaf node. (Don't think I even need it!) public static Node NULL; // initialize NULL node: static { NULL = new Node(""); for (int i = 0; i < 4; i++) NULL.child[i] = NULL; NULL.color = "null"; NULL.signature = "-1"; } // One-parameter constructor (for leaves): public Node(String c) { color = c; child = new Node[4]; for (int i = 0; i < 4; i++) child[i] = Node.NULL; } // Five-parameter constructor (for internal nodes): public Node(String c, Node n0, Node n1, Node n2, Node n3) { color = c; child = new Node[4]; child[0] = n0; child[1] = n1; child[2] = n2; child[3] = n3; } } /********************************************************************/ public class SquadB{ // The input array of 0s and 1s: public static int img[][]; // The two colors, black and white: public static String color[] = {"W","B"}; // The number of nodes in the portion of the quadtree generated so far: public static int qcount = 0; // The registry of tree types: public static Vector registry = new Vector(); // The number of children for each tree type (parallels registry vector): public static Vector nodecount = new Vector(); // Main processing loop: public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st; String line; while ((line = in.readLine()) != null) { st = new StringTokenizer(line); // Get image dimensions, expand to next power of two: int n = Integer.parseInt(st.nextToken()); int m = Integer.parseInt(st.nextToken()); if (m == 0 && n == 0) break; int max = Math.max(n,m); int twopow = 1; while (twopow < max) twopow *= 2; // Input the image: img = new int[twopow][twopow]; for (int i = 0; i < n; i++) { line = in.readLine(); char bits[] = line.toCharArray(); Arrays.fill(img[i],0); for (int j = 0; j < bits.length; j++) img[i][j] = bits[j] - '0'; } // DEBUG System.out.println("twopow="+twopow); // DEBUG: display(img); // Initialize quad tree node count, registry, nodecount: qcount = 0; registry.clear(); registry.add("0"); // initially, B and W are only known signatures registry.add("1"); nodecount.clear(); nodecount.add("1"); // child count for a leaf is 1 nodecount.add("1"); Node ans = makeSquad(0,twopow-1,0,twopow-1); int sig = Integer.parseInt(ans.signature); // DEBUG: System.out.println("Answer sig = " + sig); System.out.println(qcount + " " + nodecount.get(sig)); } } /****** USED ONLY FOR DEBUGGING ********* public static void display(int[][] img) { for (int i = 0; i < img.length; i++) { for (int j = 0; j < img[0].length; j++) { System.out.print(img[i][j]); } System.out.println(); } } ****************************************/ // All the hard work gets done here: public static Node makeSquad(int top, int bottom, int left, int right) { int n = bottom-top; // Single pixel -- base case if (n == 0) { Node r = new Node(color[img[top][left]]); int loc = search(""+img[top][left]); // what color is the pixel? r.signature = ""+loc; // B & W pixels are already registered qcount++; // update quadtree node count (we may have to undo this later) return r; } // General case: recursively construct four children. // As each of the four children is generated, save its nodecount (since // a later appearance of this same tree will wipe out the nodecount): int newbottom = top + (bottom-top)/2; int newright = left + (right-left)/2; Node ul = makeSquad(top,newbottom,left,newright); int ulnodecount = Integer.parseInt((String)nodecount.get(Integer.parseInt(ul.signature))); Node ur = makeSquad(top,newbottom,newright+1,right); int urnodecount = Integer.parseInt((String)nodecount.get(Integer.parseInt(ur.signature))); Node ll = makeSquad(newbottom+1,bottom,left,newright); int llnodecount = Integer.parseInt((String)nodecount.get(Integer.parseInt(ll.signature))); Node lr = makeSquad(newbottom+1,bottom,newright+1,right); int lrnodecount = Integer.parseInt((String)nodecount.get(Integer.parseInt(lr.signature))); // See if children all represent blocks of the same color (W or B): String c = ""; for (int i = 0; i < 2; i++) if (ul.color.equals(color[i]) && ur.color.equals(color[i]) && ll.color.equals(color[i]) && lr.color.equals(color[i])) c = color[i]; // Not all one color: new node must be "Mixed" color, so subtrees stay: if (c.length() == 0) { // can't merge colors c = "M"; } // Yes: the four children don't need to be there: else { qcount -= 4; // we already counted the children, so uncount them } qcount++; // count the root of this tree // Create new node: Node r = new Node(c,ul,ur,ll,lr); // Find node's "signature" based on signatures of children: String signature = ul.signature + " " + ur.signature + " " + ll.signature + " " + lr.signature; // However, adjust this if it's an "all one color" tree: if (!c.equals("M")) { int loc = search(""+img[top][left]); // what color is the pixel? signature = ""+loc; // B & W pixels are already registered } int dup = search(signature); // Has this node type been seen before? If so, then it adds nothing // to the "child count" in this and future usages; the new node // is "not really there." int children = 0; if (dup >= 0) { nodecount.set(dup,"0"); // we don't do this for leaves, though... if (!c.equals("M")) { nodecount.set(dup,"1"); children = 1; // ... always one node in a "B" or "W" leaf } } // Otherwise, this is a new node type, so we must add up the number // of children in each subtree type (some of which may have been // set to zero in deeper levels of the recursion): else { dup = insert(signature); // add new node type to registry children = 1; // count the node itself int loc = Integer.parseInt(ul.signature); if (c.equals("M")) { children += ulnodecount; if (ul.color.equals("M")) nodecount.set(loc,"0"); } loc = Integer.parseInt(ur.signature); if (c.equals("M")) { children += urnodecount; if (ur.color.equals("M")) nodecount.set(loc,"0"); } loc = Integer.parseInt(ll.signature); if (c.equals("M")) { children += llnodecount; if (ll.color.equals("M")) nodecount.set(loc,"0"); } loc = Integer.parseInt(lr.signature); if (c.equals("M")) { children += lrnodecount; if (lr.color.equals("M")) nodecount.set(loc,"0"); } } // All done -- save the nodecount for this tree type nodecount.set(dup,""+children); // Mark the node with its signature: r.signature = ""+dup; return r; } // Registry manipulation. To insert a new signature, just append it // to the end of the registry vector. Its index is what will be stored. public static int insert(String signature) { registry.add(signature); nodecount.add("1"); return registry.size()-1; } // Registry manipulation. Search for a signature and return its // index or -1: public static int search(String signature) { return registry.indexOf(signature); } }