algorithm - 两个骑士相遇的最小移动次数
问题描述
在由 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)
解决方案
我知道答案已经被接受,但是对于片段之间的大距离,BFS 或 Dijkstra 算法将使用大量时间和资源。
但是有一个模式:当棋子之间有足够的距离(X 和 Y 方向)时,可以在两个棋子的边界框内找到最优路径,并且可以通过封闭公式推导出。更受限制或无法解决的情况也可以在恒定时间内识别出来。区分不同模式的代码非常“乏味”,但是当路径很长时它肯定会运行得更快:在恒定时间内(如果我们假设算术运算使用恒定时间)。
这是一些 JavaScript 代码,其中还包含 BFS 算法,因此可以比较结果。它包括一个交互式部分,以便您可以玩棋盘尺寸和两块的位置并检查结果:
function knightDistance(rowCount, colCount, whiteX, whiteY, blackX, blackY) {
// Convert the state so to ensure that black is at the right & upper side of white, and below the diagonal
if (blackX < whiteX) return knightDistance(rowCount, colCount, blackX, blackY, whiteX, whiteY); // Swap pieces
if (blackY < whiteY) return knightDistance(rowCount, colCount, whiteX, rowCount - 1 - whiteY, blackX, rowCount - 1 - blackY); // Mirror against X axis
let diffX = blackX - whiteX;
let diffY = blackY - whiteY;
if (diffX < diffY) return knightDistance(colCount, rowCount, whiteY, whiteX, blackY, blackX); // mirror along diagonal
if (diffX == 2 && diffY == 2) return 4;
if (diffX <= 2 * diffY && diffX != 1) {
if ((diffX + diffY) % 2) return Math.floor((diffX + diffY + 1) / 6) * 2 + 1;
return Math.floor((diffX + diffY + 4) / 6) * 2;
}
if (rowCount == 1 || colCount == 2) return -1;
if (rowCount == 2 && diffX % 4 != 2 * diffY) return -1;
if (diffX + diffY > 3) {
if ((diffX + diffY) % 2) return Math.floor((diffX + 1) / 4) * 2 + 1;
return Math.floor((diffX + 3) / 4) * 2;
}
// Now rowCount > 2 and colCount > 2
// Other cases where lack of space plays a role
if (diffY == 1) {
// Now diffX == 1
if (rowCount == 3 && colCount == 3 && whiteX == whiteY) return -1;
if (whiteX == 0 && whiteY == 0 || blackX == colCount - 1 && blackY == rowCount - 1) return 4;
return 2;
}
// Now diffY == 0
if (diffX == 1) {
if (whiteY == 1 && rowCount == 3 && colCount == 3) return -1;
if (whiteY == 1 && rowCount == 3 && colCount == 4 && whiteX == 1) return 5;
return 3;
}
if (diffX == 2) {
if (whiteY == 1 && rowCount == 3) return 4;
return 2;
}
// Now diffY == 3
if (colCount == 4 && (whiteY == 0 || whiteY == rowCount - 1)) return 5;
return 3;
}
// The BFS algorithm for verification of the above function
function knightDistanceBfs(rowCount, colCount, whiteX, whiteY, blackX, blackY) {
let visited = new Set;
let frontier = [[whiteX, whiteY]];
visited.add(whiteX + whiteY * colCount);
let steps = 0;
while (frontier.length) {
let newFrontier = [];
for (let [whiteX, whiteY] of frontier) {
if (whiteX == blackX && whiteY == blackY) return steps;
for (let [dx, dy] of [[-2, -1], [2, -1], [2, 1], [-2, 1], [-1, -2], [1, -2], [1, 2], [-1, 2]]) {
let newX = whiteX + dx;
let newY = whiteY + dy;
if (newX < 0 || newY < 0 || newX >= colCount || newY >= rowCount) continue;
let key = newX + newY * colCount;
if (visited.has(key)) continue;
visited.add(key);
newFrontier.push([newX, newY]);
}
}
steps++;
frontier = newFrontier;
}
return -1;
}
// Quick test of all possibilities on boards with at most 5 rows and 5 columns:
for (let rowCount = 1; rowCount <= 5; rowCount++) {
for (let colCount = 1; colCount <= 5; colCount++) {
for (let whiteX = 0; whiteX < colCount; whiteX++) {
for (let whiteY = 0; whiteY < rowCount; whiteY++) {
for (let blackX = 0; blackX < colCount; blackX++) {
for (let blackY = 0; blackY < rowCount; blackY++) {
let answer = knightDistanceBfs(rowCount, colCount, whiteX, whiteY, blackX, blackY);
let answer2 = knightDistance(rowCount, colCount, whiteX, whiteY, blackX, blackY);
if (answer !== answer2) {
console.log({rowCount, colCount, whiteX, whiteY, blackX, blackY});
throw "Test case failed";
}
}
}
}
}
}
}
// I/O handling
let [rowInput, colInput] = document.querySelectorAll("input");
let table = document.querySelector("table");
let outputs = document.querySelectorAll("span");
let whiteX, whiteY, blackX, blackY;
rowInput.oninput = colInput.oninput = function () {
// Create table
table.innerHTML = "";
for (let i = +rowInput.value; i > 0; i--) {
let row = table.insertRow();
for (let j = +colInput.value; j > 0; j--) {
row.insertCell();
}
}
whiteX = -1;
blackX = -1;
};
table.onclick = function (e) {
if (e.target.tagName != "TD") return;
let x = e.target.cellIndex;
let y = e.target.parentNode.rowIndex;
if (x == whiteX && y == whiteY) {
e.target.textContent = "";
whiteX = -1;
whiteY = -1;
} else if (x == blackX && y == blackY) {
e.target.textContent = "";
blackX = -1;
blackY = -1;
} else if (whiteX == -1) {
e.target.textContent = "♘";
whiteX = x;
whiteY = y;
} else {
if (blackX != -1) { // Remove black piece first
table.rows[blackY].cells[blackX].textContent = "";
}
e.target.textContent = "♞";
blackX = x;
blackY = y;
}
if (blackX != -1 && whiteX != -1) {
outputs[0].textContent = knightDistanceBfs(+rowInput.value, +colInput.value, whiteX, whiteY, blackX, blackY);
outputs[1].textContent = knightDistance(+rowInput.value, +colInput.value, whiteX, whiteY, blackX, blackY);
} else {
outputs[0].textContent = outputs[1].textContent = "--";
}
}
rowInput.oninput();
table { border-collapse: collapse; cursor: pointer; margin: 2px }
td { border: 1px solid; width: 22px; height: 22px; padding: 0 }
input { width: 3em }
<div>Rows: <input id="rows" type="number" value="3"> Columns: <input id="cols" type="number" value="3"></div>
<table></table>
Number of moves: <span>--</span> (with BFS: <span>--</span>)
<div>Click on the board to place/remove pieces</div>
推荐阅读
- ssh - 如何通过链接 ssh
- python - 使用python selenium下载pdf无法检索嵌入框架中的url
- linux - 确定如何调用 linux 进程
- java - Java 使用哪种算法进行乘法运算?
- nginx - Nginx 上 Drupal 的 AMP 参数错误
- reactjs - 为什么我无法从另一台计算机连接到我的 create-react-app 本地开发服务器?
- php - GMail 创建转发解决另一个域范围的委派问题 - PHP
- discord - 不和谐机器人如何在线?
- python - 用猜出的字母代替破折号/ Hangman / Python
- javascript - 返回一个数字在数组中的位置