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()【陈宣之 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()