两个马相遇的最少步数

Question

在一个M行N列的棋盘上（比如8x10），有两个马，用户自己输入坐标（比如（2, 4）是白马，（7, 9）是黑骑士）。每个骑士都位于它的牢房中，但有可能两个骑士都在同一个牢房中。骑士按照棋子的走法规则轮流走棋（白马先走）。游戏的目标是尽快将两匹马放在同一个格子里。

输入格式

文件的第一行包含值M和N（2≤M，N≤1000）。第二行和第三行分别包含白骑士和黑骑士所在的单元格的坐标。第一个坐标在1到M范围内，第二个坐标在1到N范围内。

输出格式

打印一个数字——完成游戏所需的步数。如果永远不能将马放在同一个方格中，打印-1。

由于我是算法和数据结构的新手，所以我尝试这样解决这个问题：运行 for loop on all 64 possible combinations of two moves of a white and black knight, make a move对于每个骑士（检查是否超出范围），检查是否匹配，如果有，则输出。然后运行当前里面的同一个循环。同时统计走法，也输出。但是，我遇到过这样一个问题，我无法在循环内部自动执行运行ning这个循环的过程，我无法知道这个循环需要运行的次数。我试图创建一个递归函数，如果尚未找到匹配项，则可以在其中调用此循环，但我失败了。我决定用这种方式解决这个问题是行不通的，所以我研究了通常用于此类任务的算法。我正在考虑以某种方式为两匹马创建一个邻接列表，其中顶点是马的所有计算位置；使用 BFS，或 Dijkstra 算法。

已解决。这是我的 swift 代码：

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)

Answer 1

这似乎是您想要的基本逻辑，其中 ?_locs 是一组特定骑士可以位于的位置（初始化为其初始位置），one_move 产生一组从参数中的位置之一移动 1 次可到达的位置：

while bk_locs intersect wh_locs is empty:
    bk_locs = one_move(bk_locs)
    wh_locs = one_move(wh_locs)

这不能处理的是计算步数（微不足道）或确定何时放弃（更难）。

Answer 2

我知道答案已经被接受，但是对于块之间的大距离，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>

两个马相遇的最少步数

The minimum number of moves for which two knights will meet

algorithm

breadth-first-search

shortest-path

dijkstra

chess