AKnight's Journey/강소현

import java.util.Scanner;
public class Main{
	public static int [][] savePath;
	public static int [][] direct = {{-1,-2},{1,-2},{-2,-1},{2,-1},{-2,1},{2,1},{-1,2},{1,2}};
	public static void main(String [] args){
		Scanner sc = new Scanner(System.in);
		int count = sc.nextInt();
		for(int i=1; i<=count; i++){
			int p = sc.nextInt();
			int q = sc.nextInt();
			System.out.println("Scenario #"+i+":");
			int [][] path = new int[p+1][q+1];
			savePath =  new int[p*q][2];
			if(isPromising(1,1, path,0)){
				for(int k=0; k<savePath.length; k++){
					System.out.printf("%c%d",savePath[k][1]+64, savePath[k][0]);
				}
			}else
				System.out.print("impossible");
			System.out.println("\n");
		}
	}
	private static boolean isPromising(int p, int q, int [][] path, int count){
		if(p>=path.length || q>=path[0].length || p<1 || q<1 || path[p][q] == 1)
			return false;
		path[p][q] = 1;
		if(count == savePath.length-1){
			savePath[count][0] = p;
			savePath[count][1] = q;
			return true;
		}else{
			for(int i=0; i<direct.length; i++){
				if(isPromising(p+direct[i][0], q+direct[i][1], path, count+1)){
					savePath[count][0] = p;
					savePath[count][1] = q;
					return true;
				}
			}
			path[p][q] = 0;
			return false;
		}		
	}
}