Quad Trees

From Progteam

Revision as of 05:21, 21 March 2009 by Jinho (Talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search
Checkmark.jpg This problem has been solved by jinho.



Quad Trees
Problem Number 1610
Sorter: Uncategorized
Source: Unknown
Link: 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];
			
			//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];
	}
}

Personal tools