在M行N列的棋盤上（例如8x10），有兩個馬，用戶自己輸入坐標（例如，（2, 4）是白馬，（7, 9）是黑馬騎士）。每個騎士都位于其所在的單元格中，但兩個騎士也可能位于同一個單元格中。騎士按照棋子的走位規則（白馬先走）輪流走棋。游戲的目標是盡快將兩匹馬放在同一個牢房中。
輸入格式
檔案的第一行包含值 M 和 N (2≤M,N≤1000)。第二行和第三行分別包含白騎士和黑騎士所在單元格的坐標。第一個坐標在 1 到 M 的范圍內，第二個坐標在 1 到 N 的范圍內。
輸出格式
列印一個數字——完成游戲所需的移動次數。如果騎士永遠不能放置在同一個方塊中，則列印 -1。
由于我是演算法和資料結構的新手，我嘗試像這樣解決這個問題：在白騎士和黑騎士的兩個移動的所有 64 種可能組合上運行 for 回圈，為每個騎士移動（檢查它是否超出范圍），檢查是否有匹配，如果有，則輸出它。然后在電流內部運行相同的回圈。同時，對移動進行計數并輸出。但是，我遇到了這樣一個問題，我無法在回圈內部自動運行這個回圈的程序，我無法知道這個回圈需要運行的次數。我嘗試創建一個帶有遞回的函式，如果尚未找到匹配項，則可以在其中呼叫此回圈，但我失敗了。我決定這樣解決這個問題是行不通的，所以我查看了這些任務中通常使用的演算法。我想以某種方式為兩匹馬創建一個鄰接表，其中的頂點都是馬的計算位置；使用 BFS 或 Dijkstra 演算法。
解決了。這是我的快速代碼：
import Foundation
let mnstr = readLine()?.components(separatedBy: " ")
let m = Int(mnstr![0])!
let n = Int(mnstr![1])!
let wstr = readLine()?.components(separatedBy: " ")
let bstr = readLine()?.components(separatedBy: " ")
var w: [Int] = []
var b: [Int] = []
var count: Int = 0
let moves: [[Int]] = [[2, -1], [1, 2], [-2, -1], [1, -2], [2, 1], [-1, 2], [-2, 1], [-1, -2]]
w.append(Int(wstr![0])!)
w.append(Int(wstr![1])!)
b.append(Int(bstr![0])!)
b.append(Int(bstr![1])!)
var wp: Set = [w]
var bp: Set = [b]
func oneMove(lst: Set<[Int]>) -> Set<[Int]>{
let curr = lst
var out = lst
for i in curr {
for move in moves {
let item = [i[0] move[0], i[1] move[1]]
if item[0] < 1 || item[0] > m || item[1] < 1 || item[1] > n {
continue
}
out.insert(item)
}
}
return out
}
while bp.intersection(wp).isEmpty == true {
wp = oneMove(lst: wp)
count = 1
if wp.intersection(bp).isEmpty != true {
break
}
bp = oneMove(lst: bp)
count = 1
if wp.intersection(bp).isEmpty != true {
break
}
if wp.count == 1 || bp.count == 1 {
count = -1
break
}
}
print(count)
uj5u.com熱心網友回復：
這似乎是您想要的基本邏輯，其中?_locs是特定騎士可以位于的一組位置（初始化為其初始位置）并one_move產生一組可以從其中一個位置移動一次即可到達的位置在論證中：
while bk_locs intersect wh_locs is empty:
bk_locs = one_move(bk_locs)
wh_locs = one_move(wh_locs)
這不能處理的是計算移動（微不足道）或確定何時放棄（更難）。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/350530.html
上一篇：CodewarsBuddyPairsKata優化Python解決方案
下一篇：帶有扭曲演算法的BFS最短路徑