# Poj Solution 2488

```http://poj.org/problem?id=2488

import java.io.PrintWriter;
import java.util.Scanner;
import java.util.Stack;
public class Main {
static class Point{
int x ,y;
public Point(int x ,int y){
this.x = x;
this.y = y;
}
}

static int[][] chessboard = new int[27][27];
static int num = 1;
static int[] DX = {-1,1,-2,2,-2,2,-1,1};
static int[] DY = {-2,-2,-1,-1,1,1,2,2};

public static void main(String[] args) {
Scanner scn = new Scanner(System.in);

PrintWriter out = new PrintWriter(System.out);
int n ,p,q;
n = scn.nextInt();
int index = 1;
while(n-- > 0){
p = scn.nextInt();
q = scn.nextInt();
out.format("Scenario #%d:n%snn", index++,calute(p,q));
}
out.flush();
}
static boolean find;//�ҵ���־
private static String calute(int p, int q) {
//Queue<Point> points = new LinkedList<Point>();
Stack<String> result = new Stack<String>();
num = 1;
find = false;
int[][] visited = new int[p][q];
visited[0][0] = 1;
bfs(p,q,new Point(0,0),result,visited);
if(!find){
return "impossible";
}
return getResult(result);
}
private static String getResult(Stack<String> result) {
StringBuffer sbf = new StringBuffer("");
for(String str : result){
sbf.append(str);
}
return sbf.toString();
}
private static void bfs(int p, int q, Point point, Stack<String> result, int[][] visited) {
int x = point.x, y = point.y, nx,ny;
if(num == (p*q)){
find = true;
}
for(int i = 0; i < 8 && !find; i++){
nx = x + DX[i];
ny = y + DY[i];

if((nx <0 || nx >= p) || (ny < 0 || ny >= q)){
continue;
}
//�ѷ��ʹ�
if(visited[nx][ny] == 1){
continue;
}
result.add((char)('A' + ny) + "" + (nx + 1));
visited[nx][ny] = 1;
num++;
bfs(p,q,new Point(nx,ny),result,visited);
if(find){
break;
}
visited[nx][ny] = 0;
num--;
result.pop();

}
}

}

```
This entry was posted in poj. Bookmark the permalink.