Blue Bridge Cup algorithm training vault Python 100 points

Yes 8 * 8 The board , To better describe the location , Then use 0 - 63 In octal notation , First define the basic functions and variables

move = [(-1, -2), (-2, -1), (-1, 2), (2, -1), (1, 2), (2, 1), (1, -2), (-2, 1)]
# The number of steps mark moved
def idx2loc(num):
# Checkerboard index -> Line position
string = oct(num)[2:]
if len(string) == 1:
return 0, int(string)
else:
return int(string[0]), int(string[1])
def loc2idx(row, col):
# Line position -> Checkerboard index
return int(f"0o{row}{col}", 8)

Then I give out the adjacency matrix

from math import inf
adj = [[inf for _ in range(64)] for _ in range(64)]
for idx in range(64):
row, col = idx2loc(idx)
for r_, c_ in move:
r_ += row
c_ += col
# Get the next position of the horse
if 0 <= r_ < 8 and 0 <= c_ < 8:
# Determine if the next position of the horse is legal
adj[idx][loc2idx(r_, c_)] = 1

math In the library inf I think it's very easy to use , This inf + 1 Or is it equal to inf, There's a lot of conformity inf The nature of

And then directly Dijkstra Find the shortest path

def Dijkstra():
dist = [[inf, True] for _ in range(64)]
dist[loc2idx(xb, yb)][0] = 0
end = loc2idx(xe, ye)
while 1:
min_idx = -1
min_val = inf
for idx, (dis, flag) in enumerate(dist):
if flag and dis < min_val:
min_val = dis
min_idx = idx
# find min_idx, min_dist
if min_idx != -1:
dist[min_idx][1] = False
for idx, (dis, flag) in enumerate(dist):
if flag:
state = min_val + adj[min_idx][idx]
dist[idx][0] = min([state, dist[idx][0]])
else:
return dist[end][0]

Full marks end