autozzz
3 天前
把 op 的回答复制给 gork,gork 也可以，结构也是对的，思考过程的代码：
import itertools
# Define the grid
rows = 5 # 0 to 4
cols = 8 # 0 to 7
all_points = [(x, y) for x in range(cols) for y in range(rows)]
# Forbidden points
forbidden = {(0,0), (0,1), (3,1), (5,4), (7,3), (7,4)}
valid_points = [p for p in all_points if p not in forbidden]
num_valid = len(valid_points)
print(f"Number of valid points: {num_valid}")
# Function to get neighbors
def neighbors(point):
x, y = point
cand = [(x+1,y), (x-1,y), (x,y+1), (x,y-1)]
return [p for p in cand if 0 <= p[0] < cols and 0 <= p[1] < rows and p in valid_points]
# Build adjacency list
adj = {p: neighbors(p) for p in valid_points}
# Backtracking to find Hamiltonian path starting from (1,0)
start = (1, 0)
def dfs(current, visited, path):
if len(path) == num_valid:
return path
for neigh in adj[current]:
if neigh not in visited:
visited.add(neigh)
path.append(neigh)
result = dfs(neigh, visited, path)
if result:
return result
path.pop()
visited.remove(neigh)
return None
# Run the search
visited = set([start])
path = [start]
result = dfs(start, visited, path)
if result:
print("Path found:")
for p in result:
print(p)
else:
print("No path found")