【OD机试题解法笔记】跳马

题目描述

输入 m 和 n 两个数， m 和 n 表示一个 m*n 的棋盘。输入棋盘内的数据。棋盘中存在数字和 “.” 两种字符，如果是数字表示该位置是一匹马，如果是 “.” 表示该位置为空的，棋盘内的数字表示为该马能走的最大步数。例如棋盘内某个位置一个数字为 k ，表示该马只能移动 1~k 步的距离。棋盘内的马移动类似于中国象棋中的马移动，先在水平或者垂直方向上移动一格，然后再将其移动到对角线位置。棋盘内的马可以移动到同一个位置，同一个位置可以有多匹马。请问能否将棋盘上所有的马移动到同一个位置，若可以请输入移动的最小步数。若不可以输出 0 。

输入描述
输入 m 和 n 两个数， m 和 n 表示一个 m*n 的棋盘。输入棋盘内的数据。

输出描述
能否将棋盘上所有的马移动到同一个位置，若可以请输入移动的最小步数。若不可以输出 0 。

用例1
输入

3 2
. .
2 .
. .

输出

0

用例2

输入

3 5
4 7 . 4 8
4 7 4 4 .
7 . . . .

输出

17

思考

马走位和中国象棋类似，走“日字”路，以当前位置为中心，先水平移动一格再垂直移动两格或反过来，这样有八个位置：

    ·   ○   ·   ○   ·
    ○   ·   ·   ·   ○
    ·   ·  马  ·   ·
    ○   ·   ·   ·   ○
    ·   ○   ·   ○   ·

题目表述“先在水平或者垂直方向上移动一格，然后再将其移动到对角线位置”感觉不够清晰。这个对角线是相对未移动前沿着某个方向跨两格的对角线，容易理解错！接着容易想到暴力解法：先把每匹马的位置收集到一个集合中，再预处理每匹马能够到达矩阵中的所有位置并记录花费的步数，用 BFS 遍历比较方便，以马的位置为中心，一圈圈向周围扩展，不会遗漏。预处理得到 reachable 集合，关联了每个马能到达的所有位置，然后对 reachable 中每匹马的能到达的位置集合求交集。遍历交集中每个公共点，计算总步数，更新最少步数。没有交集就返回 0 。

算法过程

算法过程描述

1. 输入处理

   • 读取棋盘尺寸 m × n 和棋盘数据，标记所有马的位置及其最大步数 k。

2. BFS预处理每匹马的可达位置

   • 对每个马 (i,j,k)，执行 BFS，计算其在 k 步内能到达的所有位置及最小步数。
   • 移动方向：8 个“日”字形方向（类似象棋马）。
   • 步数限制：每次移动算 1 步，最多走 k 步。

3. 寻找公共可达位置

   • 取所有马的可达位置的交集，若无公共位置，直接返回 0。

4. 计算最小总步数

   • 对每个公共位置，累加所有马到达该位置的步数，取最小值。

5. 输出结果

   • 返回最小总步数，若无解则输出 0。

时空复杂度分析

1. 时间复杂度

   • 每匹马 BFS：O(k × m × n)（最多扩展 k 层，每层最多 m × n 个位置）。
   • N 匹马总时间：O(N × k × m × n)，其中 N ≤ m × n。

2. 空间复杂度

   • 存储每匹马的可达位置：O(N × m × n)（最坏情况下每匹马可能访问所有位置）。
   • BFS 队列：O(m × n)。

参考代码

function solution() {
  const [m, n] = readline().split(' ').map(Number);
  let matrix = Array(m);
  let horses = [];
  
  for (let i = 0; i < m; i++) {
    matrix[i] = readline().split(' ').map((e, j) => {
      if (e === '.') return '.';
      horses.push({x: i, y: j, k: Number(e)});
      return Number(e);
    });
  }

  if (horses.length === 0) {
    console.log(0);
    return;
  }

  // 中国象棋马的8个移动方向
  const directions = [
    [-2, -1], [-2, 1], [-1, -2], [-1, 2],
    [1, -2], [1, 2], [2, -1], [2, 1]
  ];

  // 预处理每个马的可达位置和步数
  const reachable = [];
  for (const horse of horses) {
    const visited = new Map();
    const queue = [[horse.x, horse.y, 0]];
    visited.set(`${horse.x},${horse.y}`, 0);

    while (queue.length) {
      const [x, y, steps] = queue.shift();
      
      if (steps >= horse.k) continue;
      
      for (const [dx, dy] of directions) {
        const nx = x + dx;
        const ny = y + dy;
        if (nx >= 0 && nx < m && ny >= 0 && ny < n) {
          const key = `${nx},${ny}`;
          if (!visited.has(key) || steps + 1 < visited.get(key)) {
            visited.set(key, steps + 1);
            queue.push([nx, ny, steps + 1]);
          }
        }
      }
    }
    reachable.push(visited);
  }

  // 找到所有马都能到达的位置
  let commonPositions = new Set(reachable[0].keys());
  for (let i = 1; i < reachable.length; i++) {
    const current = new Set(reachable[i].keys());
    commonPositions = new Set([...commonPositions].filter(pos => current.has(pos)));
    if (commonPositions.size === 0) break;
  }

  if (commonPositions.size === 0) {
    console.log(0);
    return;
  }

  // 计算最小总步数
  let minTotal = Infinity;
  for (const pos of commonPositions) {
    let total = 0;
    for (const map of reachable) {
      total += map.get(pos);
    }
    minTotal = Math.min(minTotal, total);
  }

  console.log(minTotal === Infinity ? 0 : minTotal);
}

const cases = [
`3 2
. .
2 .
. .`,
`3 5
4 7 . 4 8
4 7 4 4 .
7 . . . .`
];

let caseIndex = 0;
let lineIndex = 0;

const readline = (function () {
  let lines = [];
  return function () {
    if (lineIndex === 0) {
      lines = cases[caseIndex]
        .trim()
        .split("\n")
        .map((line) => line.trim());
    }
    return lines[lineIndex++];
  };
})();

cases.forEach((_, i) => {
  caseIndex = i;
  lineIndex = 0;
  solution();
});