(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
 This problem has been solved by jinho.

 Sorter: Uncategorized Unknown http://acm.pku.edu.cn/JudgeOnline/problem?id=1610

Quad Trees is problem number 1610 on the Peking University ACM site. This is a quad tree creation/traversal problem. It requires the use of Breadth First Search (BFS)

## Solution

```// 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];

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);
try{
} 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
*/
}

/*
* 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;
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
return l;
} else {
//Creating a leaf
return l;
}
}

/*
* it's binary number representation
*/
//Is going to store the binary representation of the quad tree
String num = "";

//Queue as required by the BFS algorithm
//Enqueue the root

while(q.size() > 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
}
}
}
return num;
}
}

boolean hasChildren;
String value;