# AKnight's Journey/강소현

## Status ¶

 Problem 2488 User talin0528 Memory 3852K Time 360MS Language Java Result Accepted

## Source Code ¶

```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;
}
}
}
```