สมมติว่ามีกระดานหมากและชิ้นหมากพิเศษ K ที่เคลื่อนที่แบบตัวแอลภายในกระดาน หากชิ้นหมากอยู่ที่ (x1, y1) และเคลื่อนไป (x2, y2) การเคลื่อนที่อธิบายได้ว่า x2 = x1 ± a; y2 = y1 ± b หรือ x2 = x1 ± b; y2 = y1 ± a โดยที่ a และ b เป็นจำนวนเต็ม เราต้องหาจำนวนการเคลื่อนที่น้อยที่สุดเพื่อไปถึงตำแหน่ง (n-1, n-1) จาก (0, 0) หากตำแหน่งไหนไปไม่ได้ จะแสดง -1 มิฉะนั้นแสดงจำนวนการเคลื่อนที่ จะพิมพ์ n-1 บรรทัด แต่ละบรรทัด i มี n-1 จำนวนเต็มอธิบายจำนวนการเคลื่อนที่สำหรับแต่ละ j
ตัวอย่างอินพุตและเอาต์พุต
n = 6 → ผลลัพธ์เป็นตาราง 5x5 ตามภาพและข้อความ
ขั้นตอนการแก้ปัญหา
นิยามฟังก์ชัน
path_search(i, j, n)ใช้ BFS หาทางสั้นที่สุดสร้างคิวเริ่มต้นที่ (0,0) และกำหนดทิศทางเคลื่อนที่ 8 ทิศทางของナイト
ค้นหาแบบ BFS จนถึง (n-1, n-1) แล้วนับย้อนกลับหาจำนวนก้าว
ฟังก์ชันหลัก
solve(n)สร้างตารางผลลัพธ์ โดยใช้สมметรีย์และเงื่อนไขพิเศษสำหรับ i=j
โค้ดต้นฉบับ (Python)
from collections import defaultdict
def path_search(i, j, n):
temp_list = defaultdict(lambda: (-1,-1))
queue_positional = [(0, 0)]
ver = [(i, j), (-i, j), (i, -j), (-i, -j), (j, i), (j, -i), (-j, i), (-j, -i)]
while len(queue_positional) > 0:
current_element = queue_positional.pop(0)
for element in ver:
x = element[0] + current_element[0]
y = element[1] + current_element[1]
if -1 < x < n and -1 < y < n and temp_list[x, y] == (-1,-1):
temp_list[x, y] = current_element
queue_positional.append((x, y))
if x == n - 1 and y == n - 1:
count_var = 1
while temp_list[x,y] != (0,0):
count_var += 1
x, y = temp_list[x,y]
return count_var
return -1
def solve(n):
board = defaultdict(lambda: -1)
for i in range(1, n):
for j in range(1, i):
if board[i, j] == -1:
board[i, j] = path_search(i, j, n)
board[j, i] = board[i, j]
if (n - 1) % i == 0:
board[i, i] = (n - 1) / i
for i in range(1, n):
for j in range(1, n - 1):
print(int(board[i, j]), end=' ')
print(int(board[i, n - 1]))
solve(6)
อินพุต
6
เอาต์พุต
5 4 3 2 5 4 -1 2 -1 -1 3 2 -1 -1 -1 2 -1 -1 -1 -1 5 -1 -1 -1 1
