02488: A Knight's Journey
http://cs101.openjudge.cn/practice/02488/
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来源
TUD Programming Contest 2005, Darmstadt, Germany
思路：通过回溯法枚举所有可能路径，并优化提高搜索效率。
回溯法：从起点开始，尝试所有合法移动方向。标记已访问方格，递归探索下一个位置。若访问完所有方格，记录路径；若无路可走，回溯并尝试其他方向。
优化：按列字母（A, B, ...）和行号（1, 2, ...）升序尝试移动，确保找到的第一条路径即为字典序最小。并且，若当前路径无法覆盖所有方格，提前终止该分支。
def knight_tour(p, q):
moves = [(-2, -1), (-2, 1), (-1, -2), (-1, 2), (1, -2), (1, 2), (2, -1), (2, 1)]
total = p * q
path = []
visited = [[False for _ in range(q)] for _ in range(p)]
def backtrack(row, col):
path.append(f"{chr(ord('A') + col)}{row + 1}")
visited[row][col] = True
if len(path) == total:
return True
next_steps = []
for dr, dc in moves:
nr, nc = row + dr, col + dc
if 0 <= nr < p and 0 <= nc < q and not visited[nr][nc]:
next_steps.append((nc, nr))
for nc, nr in sorted(next_steps):
if backtrack(nr, nc):
return True
path.pop()
visited[row][col] = False
return False
for start_row in range(p):
for start_col in range(q):
if backtrack(start_row, start_col):
return ''.join(path)
return "impossible"
n = int(input())
for i in range(n):
p, q = map(int, input().split())
result = knight_tour(p, q)
print(f"Scenario #{i+1}:")
print(result)
print()在 Python 中实现该算法时，我们需要注意递归深度以及 Python 对象的开销。题目约束
以下是对应的 Python 代码实现：
import sys
# 增加递归深度限制，防止深层搜索时溢出
sys.setrecursionlimit(2000)
def solve():
# 读取所有输入数据
input_data = sys.stdin.read().split()
if not input_data:
return
n_test_cases = int(input_data[0])
current_idx = 1
# 定义骑士的 8 个跳跃方向
# 关键点：为了保证字典序最小，必须严格按照以下顺序排列：
# 优先选择列偏移（字母）最小的方向；若列偏移相同，选择行偏移（数字）最小的方向。
moves = [
(-2, -1), (-2, 1), (-1, -2), (-1, 2),
(1, -2), (1, 2), (2, -1), (2, 1)
]
for case_num in range(1, n_test_cases + 1):
# p 是行数 (数字 1-p)，q 是列数 (字母 A-...)
p = int(input_data[current_idx])
q = int(input_data[current_idx + 1])
current_idx += 2
total_cells = p * q
path = []
# 记录已访问格子的位掩码 (Bitmask)
# 位索引计算公式: col_index * p + (row_index - 1)
def dfs(curr_c, curr_r, mask, count):
# 如果访问的格子数等于总数，说明找到了路径
if count == total_cells:
return True
for dc, dr in moves:
nc, nr = curr_c + dc, curr_r + dr
# 边界检查
if 0 <= nc < q and 1 <= nr <= p:
bit_pos = nc * p + (nr - 1)
# 检查该位置是否已访问
if not (mask & (1 << bit_pos)):
# 记录当前路径
path.append(f"{chr(ord('A') + nc)}{nr}")
# 递归搜索
if dfs(nc, nr, mask | (1 << bit_pos), count + 1):
return True
# 回溯：如果该方向不通，弹出路径
path.pop()
return False
print(f"Scenario #{case_num}:")
# 字典序剪枝：直接从 A1 (col=0, row=1) 开始搜索
# 如果从 A1 出发无解，则由于对称性，其他起点的解字典序必然更大或同样无解
start_col, start_row = 0, 1
path.append("A1")
initial_mask = 1 << (0 * p + (1 - 1))
if dfs(start_col, start_row, initial_mask, 1):
print("".join(path))
else:
print("impossible")
# 每组案例后输出一个空行（题目要求）
print()
if __name__ == "__main__":
solve()代码解读与优化要点：
- 方向数组 (Move Ordering)：
moves列表中的顺序是解题的核心。例如(-2, -1)代表列向左移动 2 格，行向上移动 1 格。这在所有 8 个方向中是字典序最小的（字母减得最多，数字减得也多）。- 只要按此顺序搜索，找到的第一个有效解就一定是字典序最小的解。
- 位掩码 (Bitmask)：
- 在 Python 中，整数是任意精度的，因此我们可以像 C++ 那样使用位运算。
mask | (1 << bit_pos)用于标记格子，mask & (1 << bit_pos)用于检查。这比使用二维列表visited[p][q]性能更好。
- 坐标映射：
- 题目中的
p表示数字（行），q表示字母（列）。 - 在代码中，我将列索引映射为
0到q-1，行映射为1到p。 - 输出时，使用
chr(ord('A') + nc)将数字列索引转回大写字母。
- 题目中的
- 起点固定策略：
- 由于需要字典序最小，起点必为
A1。 - 本题限制
，这意味着搜索空间虽然理论上很大，但在实际运行中，由于路径必须覆盖所有格子，约束极强，DFS 会很快触发回溯或找到解。
- 由于需要字典序最小，起点必为
【陈宣之 23生科】思路：Dijstra，把路径放在第一位，用heapq取字典序最小
# 陈宣之 23生科
import heapq
def dfs(x,y,r,c):
global table,directions
q=[[table[x][y],(x,y)]]
while q:
way,(x,y)=heapq.heappop(q)
if len(way)==r*c*2:
return way
for dx,dy in directions:
nx,ny=x+dx,y+dy
if 0<=nx<r and 0<=ny<c and table[nx][ny] not in way:
heapq.heappush(q,[way+table[nx][ny],(nx,ny)])
return 0
n=int(input())
directions=[(-2,-1),(-2,1),(-1,2),(-1,-2),(1,-2),(1,2),(2,-1),(2,1)]
for _ in range(n):
p,q=map(int,input().split())
table=[]
for i in range(p):
temp=[]
for j in range(q):
temp.append(chr(ord("A")+j)+str(i+1))
table.append(temp)
judge=False
for j in range(q):
for i in range(p):
if dfs(i,j,p,q):
judge=True
print("Scenario #",_+1,":",sep="")
print(dfs(i,j,p,q))
break
if judge:
break
if not judge:
print("Scenario #",_+1,":",sep="")
print("impossible")
if _<n-1:
print()回溯即可，重点是需要排列好自己的方向使得第一个弄出来的就是字典序第一个。
# 曹以楷
"""
@File : knights_journey_02488.py
@Time : 2025/03/07 18:59:38
@Author : Usercyk
@Description : Get the possible paths for a knight to pass every squares in pxq board.
"""
class Solution:
"""
The solution class
"""
MOVES = [(-2, -1), (-2, 1), (-1, -2), (-1, 2),
(1, -2), (1, 2), (2, -1), (2, 1)]
def __init__(self) -> None:
self.path = []
self.p = -1
self.q = -1
self.board = []
self.flag = False
def travel(self, step: int = 1, x: int = 0, y: int = 0) -> bool:
"""
Travel the pxq board
Arguments:
step -- the current step
x -- current pos x
y -- current pos y
Returns:
Can the knight travel through all the board
"""
if step == self.p*self.q:
self.flag = True
return True
for dy, dx in self.MOVES:
nx, ny = x+dx, y+dy
if all((not self.flag, 0 <= nx < self.p, 0 <= ny < self.q)):
if self.board[nx][ny] != 1:
self.board[nx][ny] = 1
self.path[step] = (nx, ny)
self.travel(step+1, nx, ny)
self.board[nx][ny] = 0
return self.flag
def re_init(self, p: int, q: int):
"""
Init the board and paths
Arguments:
p -- the numbers
q -- the alphabets
"""
self.p, self.q = p, q
self.path = [(0, 0) for _ in range(p*q)]
self.board = [[0]*(q+1) for _ in range(p+1)]
self.board[0][0] = 1
self.flag = False
def solve(self):
"""
Solve the problem
"""
for i in range(int(input())):
self.re_init(*map(int, input().split()))
print(f"Scenario #{i+1}:")
if self.travel():
ans = (chr(c[1]+ord("A"))+str(c[0]+1) for c in self.path)
print("".join(ans))
else:
print("impossible")
print("")
if __name__ == "__main__":
Solution().solve()move = [(-2, -1), (-2, 1), (-1, -2), (-1, 2), (1, -2), (1, 2), (2, -1), (2, 1)]
def dfs(x, y, step, p, q, visited, ans):
if step == p * q:
return True
for i in range(8):
dx, dy = x + move[i][0], y + move[i][1]
if 1 <= dx <= q and 1 <= dy <= p and not visited[dx][dy]:
visited[dx][dy] = True
ans[step] = chr(dx + 64) + str(dy)
if dfs(dx, dy, step + 1, p, q, visited, ans):
return True
visited[dx][dy] = False
return False
n = int(input())
for m in range(1, n + 1):
p, q = map(int, input().split())
ans = ["" for _ in range(p * q)]
visited = [[False] * (p + 1) for _ in range(q + 1)]
visited[1][1] = True
ans[0] = "A1"
if dfs(1, 1, 1, p, q, visited, ans):
result = "".join(ans)
else:
result = "impossible"
print(f"Scenario #{m}:")
print(result)
print()