2013
11-11

# A Knight’s Journey

Background

The knight is getting bored of seeing the same black and white squares again and again and has decided to make a journey

around the world. Whenever a knight moves, it is two squares in one direction and one square perpendicular to this. The world of a knight is the chessboard he is living on. Our knight lives on a chessboard that has a smaller area than a regular 8 * 8 board, but it is still rectangular. Can you help this adventurous knight to make travel plans?

Problem

Find a path such that the knight visits every square once. The knight can start and end on any square of the board.

The input begins with a positive integer n in the first line. The following lines contain n test cases. Each test case consists of a single line with two positive integers p and q, such that 1 <= p * q <= 26. This represents a p * q chessboard, where p describes how many different square numbers 1, . . . , p exist, q describes how many different square letters exist. These are the first q letters of the Latin alphabet: A, . . .

The output for every scenario begins with a line containing “Scenario #i:”, where i is the number of the scenario starting at 1. Then print a single line containing the lexicographically first path that visits all squares of the chessboard with knight moves followed by an empty line. The path should be given on a single line by concatenating the names of the visited squares. Each square name consists of a capital letter followed by a number.

If no such path exist, you should output impossible on a single line.

3
1 1
2 3
4 3

Scenario #1:
A1

Scenario #2:
impossible

Scenario #3:
A1B3C1A2B4C2A3B1C3A4B2C4


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%s\n\n", index++,calute(p,q));
}
out.flush();
}
static boolean find;//找到标志
private static String calute(int p, int q) {
Stack result = new Stack();
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 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 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();

}
}

}

1. 老实说，这种方法就是穷举，复杂度是2^n，之所以能够AC是应为题目的测试数据有问题，要么数据量很小，要么能够得到k == t，否则即使n = 30，也要很久才能得出结果，本人亲测

2. “再把所有不和该节点相邻的节点着相同的颜色”，程序中没有进行不和该节点相邻的其他节点是否相邻进行判断。再说求出来的也不一样是颜色数最少的

3. 第一句可以忽略不计了吧。从第二句开始分析，说明这个花色下的所有牌都会在其它里面出现，那么还剩下♠️和♦️。第三句，可以排除2和7，因为在两种花色里有。现在是第四句，因为♠️还剩下多个，只有是♦️B才能知道答案。

4. 题目需要求解的是最小值，而且没有考虑可能存在环，比如
0 0 0 0 0
1 1 1 1 0
1 0 0 0 0
1 0 1 0 1
1 0 0 0 0
会陷入死循环

5. 题本身没错，但是HDOJ放题目的时候，前面有个题目解释了什么是XXX定律。
这里直接放了这个题目，肯定没几个人明白是干啥