Solution.scala

package googlecodejam;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Scanner;

public class Pylons2 {
	public static void main(String[] args) {
		Scanner scan = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
		int T = scan.nextInt();
		int[] rList = new int[T];
		int[] cList = new int[T];
		for (int t = 0; t < T; t++) {
			rList[t] = scan.nextInt();
			cList[t] = scan.nextInt();
		}
		for (int t = 0; t < T; t++) {
			
			System.out.print("Case #" + (t + 1) + ": ");
			
			int iDiv = rList[t] / 5;
			int iRem = rList[t] % 5;
			if (iDiv < 1) {
				iDiv = 1;
			}
			int jDiv = cList[t] / 5;
			int jRem = cList[t] % 5;
			if (jDiv < 1) {
				jDiv = 1;
			}
			
			for (int i = 0; i < iDiv; i++) {
				for (int j = 0; j < jDiv; j++) {
					if (i == iDiv - 1) {
						if (j == jDiv - 1) {
							divideTraverse(i, iRem, j, jRem);
						} else {
							divideTraverse(i, iRem, j, 0);
						}
					} else {
						if (j == jDiv - 1) {
							divideTraverse(i, 0, j, jRem);
						} else {
							divideTraverse(i, 0, j, 0);
						}
					}
				}
			}
		}
	}
	
	private static void divideTraverse(int nI, int nIrem, int nJ, int nJrem) {
		boolean isCompleted = false;
		boolean[][] box = new boolean[5 + nIrem][5 + nJrem];
		for (int i = 0; i < 5 + nIrem; i++) {
			for (int j = 0; j < 5 + nJrem; j++) {
				box[i][j] = false;
			}
		}
		for (int i = nI * 5; i < nI * 5 + 5 + nIrem; i++) {
			for (int j = nJ; j < nJ + 5 + nJrem; j++) {
				isCompleted = traverse(box, 0, new Point(i, j), new Point(nI + nIrem, nJ + nJrem));
				if (isCompleted) {
					break;
				}
			}
			if (isCompleted) {
				break;
			}
		}
		if (!isCompleted) {
			System.out.println("IMPOSSIBLE");
		}
	}
	
	private static boolean traverse(boolean[][] newBox, int depth, Point point, Point originPoint) {
		if (depth == newBox.length * newBox[0].length - 1) {
			System.out.println("POSSIBLE");
			System.out.println(point.toString());
			return true;
		}
		newBox[point.i][point.j] = true;
		
		boolean isOdd = depth % 2 == 1;
		if (isOdd) {
			for (int i = 0; i < newBox.length; i++) {
				for (int j = 0; j < newBox[0].length; j++) {
					Point next = new Point(i, j);
					if (!isVisited(newBox, next) && isPossibleToMove(point, next)) {
						boolean isSuccess = traverse(newBox, depth + 1, next, originPoint);
						if (isSuccess) {
							System.out.println(new Point(point.i + originPoint.i, point.j + originPoint.j).toString());
							return true;
						}
					}
				}
			}
		} else {
			for (int i = newBox.length - 1; i >= 0; i--) {
				for (int j = newBox[0].length - 1; j >= 0; j--) {
					Point next = new Point(i, j);
					if (!isVisited(newBox, next) && isPossibleToMove(point, next)) {
						boolean isSuccess = traverse(newBox, depth + 1, next, originPoint);
						if (isSuccess) {
							System.out.println(new Point(point.i + originPoint.i, point.j + originPoint.j).toString());
							return true;
						}
					}
				}
			}
		}
		
		newBox[point.i][point.j] = false;
		return false;
	}
	
	private static boolean isVisited(boolean[][] box, Point next) {
		return box[next.i][next.j];
	}
	
	private static boolean isPossibleToMove(Point before, Point next) {
		if (before.i == next.i || before.j == next.j) {
			return false;
		}
		if (before.i - before.j == next.i - next.j) {
			return false;
		}
		if (before.i + before.j == next.i + next.j) {
			return false;
		}
		return true;
	}
	
	static class Point {
		public Point(int i, int j) {
			this.i = i;
			this.j = j;
		}
		
		int i, j;
		
		public String toString() {
			return (i + 1) + " " + (j + 1);
		}
	}
}