資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究Python程式：找出國際象棋棋子到達棋盤上每個位置的最少步數
假設我們有一個棋盤和一個特殊的騎士棋子 K，它在棋盤內以 L 形移動。如果棋子位於 (x1, y1) 位置，並且移動到 (x2, y2) 位置，則移動可以描述為 x2 = x1 ± a ; y2 = y1 ± b 或 x2 = x1 ± b ; y2 = y1 ± a ; 其中 a 和 b 是整數。我們需要找出該棋子從 (0, 0) 位置到達棋盤上 (n-1, n-1) 位置的最少步數。如果某個位置不可到達，則標記為 -1，否則返回步數。我們將列印 n – 1 行輸出，其中每行 i 將包含 n − 1 個整數，描述棋子為每個 j 移動所需的最小步數。
因此，如果輸入為 n = 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
如果棋子位於 5x5 棋盤上的 (3, 3) 位置，則騎士可能的移動。
第一行輸出包含棋子到達 (1,1) 到 (1,5) 位置所需的最小步數。後續行類似地描述每個相應 I 和 j 值的最小步數。
為了解決這個問題，我們將遵循以下步驟 -
定義一個函式 path_search() 。它將接收 i、j、n 作為引數。
temp_list := 初始化為 (-1, -1) 對的新對映。
queue_positional := 初始化為 (0, 0) 對的新列表。
ver := [(i, j) ,(-i, j) ,(i, -j) ,(-i, -j) ,(j, i) ,(j, -i) ,(-j, i) ,(-j, -i) ]
當 queue_positional 的大小 > 0 時，執行以下操作：
current_element := 從 queue_positional 中刪除第一個元素。
對於 ver 中的每個元素，執行以下操作：
x := element[0] + current_element[0]
y := element[1] + current_element[1]
如果 -1 < x < n 且 -1 < y < n 並且 temp_list[x, y] 與 (-1, -1) 相同，則：
temp_list[x, y] := current_element
在 queue_positional 的末尾插入 (x, y) 對。
如果 x 與 n - 1 相同且 y 與 n - 1 相同，則：
count_var := 1
當 temp_list[x,y] 與 (0, 0) 不相同 時，執行以下操作：
count_var := count_var + 1
x, y := temp_list[x,y]
返回 count_var。
返回 -1。
從主函式/方法中執行以下操作 -
board := 初始化為 -1 的新對映。
對於範圍 1 到 n 的 i，執行以下操作：
對於範圍 1 到 i 的 j，執行以下操作：
如果 board[i, j] 與 -1 相同，則：
board[i, j] := path_search(i, j, n)
board[j, i] := board[i, j]
如果 (n - 1) mod i 與 0 相同，則：
board[i, i] :=(n - 1) / i
對於範圍 1 到 n 的 i，執行以下操作：
對於範圍 1 到 n - 1 的 j，執行以下操作：
列印 board[i, j]
列印 board[i, n - 1]
原始碼 (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
530 次檢視
