Q-Tree code

[JT]

// If you put this into PKU, remember to first get rid of all
comments, otherwise you will get a compile error.

import java.io.File;
import java.io.FileNotFoundException;
import java.lang.NumberFormatException;
import java.util.Scanner;
import java.util.ArrayList;

public class Main {
static Scanner in;
public static void main(String[] args) {
try {
in = new Scanner(new File(args[0]));
initAlgorithm();
in.close();
} catch(FileNotFoundException e) {
e.printStackTrace();
}
}

public static void initAlgorithm() {
int k = in.nextInt();
//Doing each test case
for (int i = k; i > 0; i--) {
//Get grid size
int dim = in.nextInt();

//Create grid
int grid[][] = new int[dim][dim];

//Read in grid
for (int y = 0; y < dim; y++) {
for (int x = 0; x < dim; x++) {
grid[y][x] = in.nextInt();
}
}
algorithm(dim, grid);
}
}

/*
* Where we execute the algorithm to solve the problem
*/
public static void algorithm(int dim, int grid[][]) {
//Debug
//printGrid(dim, grid);
QuadTreeNode root = makeQuadTree(0, 0, dim, grid);
String num = BFSQuadTreeNodes(root);
int answer = 0;
try{
answer = Integer.parseInt(num, 2);
} catch (NumberFormatException e) {}

/* PKU can be very annoying, you can make an elaborate algorithm,
* only to get the wrong answer because you didn't capitalize your
* hexidecimal answer.
*/
System.out.println(Integer.toHexString(answer).toUpperCase());
}

/*
* splitGrid() scans the grid and determines whether it is all white
or
* all black or mixed.
* if all white returns 0
* if all black returns 1
* if mixed returns -1
*/
public static int splitGrid(int xstart, int ystart, int dim, int grid
[][]) {
//Starting color
int scolor = grid[ystart][xstart];

if (dim == 1) return scolor;

//Ok to do this since we're guaranteed that the dim is a multiple of
2
int mid = dim/2;

//Start in the middle of the grid
int xs = xstart + mid;
int ys = ystart + mid;


//Start at the leftmost x point and move the grid dimension length
right
for(int x = xstart; x < xstart + dim; x++) {
if (grid[ys][x] != scolor) return -1;
}

//Start at the topmost y point and move the grid dimension length
down
for (int y = ystart; y < ystart + dim; y++) {
if (grid[y][xs] != scolor) return -1;
}

//Else, the grid is the same color as the start color
return scolor;
}

/*
* Does the same thing as above, but apparently runs faster...I guess
that's
* Java's internal optimization at play...
*/
public static int splitGrid2(int xstart, int ystart, int dim, int grid
[][]) {
int scolor = grid[ystart][xstart];
if (dim == 1) return scolor;
for (int y = ystart; y < ystart + dim; y++) {
for (int x = xstart; x < xstart + dim; x++) {
if (grid[y][x] != scolor) return -1;
}
}
return scolor;
}

/*
* 1) Check the grid- if it's completely white or black, return a
Quad Tree
* Node that will be a leaf and contain either "00" or "01"
respectively
* 2) Otherwise we have to partition the grid into 4 pieces, and
create a
* Quad Tree Node with 4 children that represent the 4 way partition
*/
public static QuadTreeNode makeQuadTree(int xstart, int ystart, int
dim, int grid[][]) {
//int t = splitGrid(xstart, ystart, dim, grid);
int t = splitGrid2(xstart, ystart, dim, grid);
if (t < 0) {
int ndim = dim/2;
QuadTreeNode r = new QuadTreeNode("1");
r.children[0] = makeQuadTree(xstart, ystart, ndim, grid);
r.children[1] = makeQuadTree(xstart + ndim, ystart, ndim, grid);
r.children[2] = makeQuadTree(xstart, ystart + ndim, ndim, grid);
r.children[3] = makeQuadTree(xstart + ndim, ystart + ndim, ndim,
grid);
r.hasChildren = true;
return r;
} else if (t == 0) {
//Creating a leaf
QuadTreeNode l = new QuadTreeNode("00");
return l;
} else {
//Creating a leaf
QuadTreeNode l = new QuadTreeNode("01");
return l;
}
}

/*
* Using Breadth First Search to convert the Quad Tree into
* it's binary number representation
*/
public static String BFSQuadTreeNodes(QuadTreeNode root) {
//Is going to store the binary representation of the quad tree
String num = "";

//Queue as required by the BFS algorithm
ArrayList<QuadTreeNode> q = new ArrayList<QuadTreeNode>();
//Enqueue the root
q.add(root);

while(q.size() > 0) {
//Remove head of queue
QuadTreeNode n = q.remove(0);

//Do something
num = num.concat(n.value);

//For all the children
if (n.hasChildren) {
for (int i = 0; i < n.children.length; i++) {
//Enque the children in the proper order
q.add(n.children[i]);
}
}
}
return num;
}
}

class QuadTreeNode {
boolean hasChildren;
String value;
QuadTreeNode children[];

public QuadTreeNode(String value) {
this.hasChildren = false;
this.value = value;
this.children = new QuadTreeNode[4];
}
}