(C卷,200分)- 跳马（Java & JS & Python & C）

题目描述

马是象棋（包括中国象棋和国际象棋）中的棋子，走法是每步直一格再斜一格，即先横着或者直者走一格，然后再斜着走一个对角线，可进可退，可越过河界，俗称"马走日"字。

给定 m 行 n 列的棋盘（网格图），棋盘上只有棋子象棋中的棋子“马”，并且每个棋子有等级之分，等级为 k 的马可以跳 1~k 步（走的方式与象棋中“马”的规则一样，不可以超出棋盘位置），问是否能将所有马跳到同一位置，如果存在，输出最少需要的总步数（每匹马的步数相加），不存在则输出-1。

注：允许不同的马在跳的过程中跳到同一位置，坐标为（x,y）的马跳一次可以跳到的坐标为：(x+1, y+2)，(x+1, y-2)，(x+2, y+1)，(x+2, y-1)，(x-1, y+2)，(x-1, y-2)，(x-2, y+1)，(x-2, y-1)，的格点上，但是不可以超出棋盘范围。

输入描述

第一行输入m，n，代表 m 行 n 列的网格图棋盘（1 ≤ m, n ≤ 25）

接下来输入 m 行 n 列的网格图棋盘，如果第 i 行，第 j 列的元素为 "." ，代表此格点没有棋子，如果为数字 k（1 ≤ k ≤ 9），代表此格点存在等级为 k 的“马”

输出描述

输出最少需要的总步数（每匹马的步数相加），不存在则输出-1。

用例

题目解析

本题需要我们找到一个位置：

• 所有马都能跳到该位置
• 所有马跳到该位置的步数之和最小

返回该位置的最小步数和。

另外，每个马还有等级K，决定了该马能跳的步数。

因此，我们只需要遍历每一匹马，并基于BFS策略，让该马跳K步，在跳的过程中，我们记录下该马跳过的位置，马第一次跳到某位置，即为该马到达该位置的最小步数，后续该马再次跳到该位置，则非到达该位置的最小步数。

具体解题时，我们可以定义：

• stepMap：一个m行n列整型矩阵，矩阵每个元素初始值为0，stepMap[i][j]表示所有能跳到(i, j)位置的马所花费的最小步数之和
• reach：一个Set集合，用于记录所有马都能跳到的公共位置，初始时该集合记录棋盘所有位置，即认为所有马可以跳到所有位置，所有位置都是公共位置

然后，基于每一匹马进行BFS，在BFS前定义：

• 一个Set集合vis，用于记录当前马能跳到的位置
• 马的位置信息 [x, y, step]，表示马到达棋盘（x,y）位置，花费了step步，初始时，(x,y)即为马所在位置，step=0

之后从初始位置开始按层BFS跳到新位置(newX, newY)，如果新位置：

1. 越界
2. 已经跳过（新位置在vis集合中）

则新位置不可进入，其余情况可以进入新位置，进入新位置后，意味着新位置需要花费step+1步，此时该马到达新位置的最小步数即为step+1，之后：

• stepMap[newX][newY] += step + 1
• vis.add(newX * n + newY)

对马进行按层BFS，主要是为了记步，即走了几步，每一层都代表一步，因此当BFS进行了K层后，该马走了K步。

当马走完所有步数后，我们对 reach 和 vis 两个集合取交集（位置），将交集重新赋值给reach，这样就能保证reach记录的位置是所有马都能到达的公共位置。

如果最后reach集合的元素个数为0，则代表没有公共位置，此时返回-1。

否则，遍历reach中记录的公共位置，结合stepMap找到所有公共位置中的最小步数和。

JS算法源码

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

void (async function () {
  // 棋盘行数, 棋盘列数
  const [m, n] = (await readline()).split(" ").map(Number);

  // 记录所有马都可达的公共位置坐标
  const reach = new Set();

  // 棋盘矩阵
  const map = [];
  for (let i = 0; i < m; i++) {
    map.push(await readline());

    // 初始时假设所有位置都是各个马可达的
    for (let j = 0; j < n; j++) {
      reach.add(i * n + j); // 二维坐标一维化
    }
  }

  // 最小步数和矩阵，stepMap[i][j]记录各个马走到棋盘(i,j)位置的最小步数之和
  const stepMap = new Array(m).fill(0).map(() => new Array(n).fill(0));

  function getResult() {
    // 遍历棋盘
    for (let i = 0; i < m; i++) {
      for (let j = 0; j < n; j++) {
        // 如果棋盘(i,j)位置是马
        if (map[i][j] != ".") {
          // 马的等级
          const k = parseInt(map[i][j]);
          // 对该马进行BFS走日
          bfs(i, j, k);
        }
      }
    }

    // 如果所有马走完，发现没有公共可达位置
    if (reach.size == 0) {
      return -1;
    }

    // 记录所有马都可达位置的最小步数和
    let minStep = Infinity;
    for (let pos of reach) {
      const y = pos % n;
      const x = (pos - y) / n;
      // (x,y)是所有马都可达的位置，stepMap[x][y]记录所有马到达此位置的步数和
      minStep = Math.min(minStep, stepMap[x][y]);
    }

    return minStep;
  }

  // 马走日的偏移量
  const offsets = [
    [1, 2],
    [1, -2],
    [2, 1],
    [2, -1],
    [-1, 2],
    [-1, -2],
    [-2, 1],
    [-2, -1],
  ];

  // 广搜
  function bfs(sx, sy, k) {
    // 广搜队列
    // (sx,sy)为马所在初始位置，马到达初始位置需要0步
    let queue = [[sx, sy, 0]];

    // 记录该马可以访问(sx,sy)位置
    const vis = new Set();
    vis.add(sx * n + sy); // 二维坐标一维化

    // k记录该马剩余可走步数
    while (queue.length > 0 && k > 0) {
      // newQueue记录该马花费相同步数的可达的位置（即BFS按层遍历的层）
      const newQueue = [];

      // 按层BFS
      for (let [x, y, step] of queue) {
        for (let [offsetX, offsetY] of offsets) {
          // 马走日到达的新位置
          const newX = x + offsetX;
          const newY = y + offsetY;

          const pos = newX * n + newY;

          // 如果新位置越界或者已访问过，则不能访问
          if (newX < 0 || newX >= m || newY < 0 || newY >= n || vis.has(pos))
            continue;

          // 将新位置加入新层
          newQueue.push([newX, newY, step + 1]);

          // 该马到达(newX, newY)位置最小步数为step+1, 由于该马首次到达(newX, newY)位置，因此step+1就是最小步数
          stepMap[newX][newY] += step + 1;

          // 记录该马访问过该位置，后续如果该马再次访问该位置，则不是最小步数
          vis.add(pos);
        }
      }

      queue = newQueue;
      k--; // 剩余步数减1
    }

    // BFS完后，将公共可达位置reach和当前马可达位置取交集，交集部分就是新的公共可达位置
    reach.forEach((pos) => {
      if (!vis.has(pos)) {
        reach.delete(pos);
      }
    });
  }

  console.log(getResult());
})();

Java算法源码

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Scanner;

public class Main {
  // 棋盘行数
  static int m;
  // 棋盘列数
  static int n;
  // 棋盘矩阵
  static char[][] map;
  // 最小步数和矩阵，stepMap[i][j]记录各个马走到棋盘(i,j)位置的最小步数之和
  static int[][] stepMap;
  // 记录所有马都可达的公共位置坐标
  static HashSet<Integer> reach;

  // 马走日的偏移量
  static int[][] offsets = {{1, 2}, {1, -2}, {2, 1}, {2, -1}, {-1, 2}, {-1, -2}, {-2, 1}, {-2, -1}};

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);

    m = sc.nextInt();
    n = sc.nextInt();

    map = new char[m][n];
    stepMap = new int[m][n];
    reach = new HashSet<>();

    for (int i = 0; i < m; i++) {
      map[i] = sc.next().toCharArray();

      // 初始时假设所有位置都是各个马可达的
      for (int j = 0; j < n; j++) {
        reach.add(i * n + j);
      }
    }

    System.out.println(getResult());
  }

  public static int getResult() {
    // 遍历棋盘
    for (int i = 0; i < m; i++) {
      for (int j = 0; j < n; j++) {
        // 如果棋盘(i,j)位置是马
        if (map[i][j] != '.') {
          // 马的等级
          int k = map[i][j] - '0';
          // 对该马进行BFS走日
          bfs(i, j, k);
        }
      }
    }

    // 如果所有马走完，发现没有公共可达位置
    if (reach.size() == 0) {
      return -1;
    }

    // 记录所有马都可达位置的最小步数和
    int minStep = Integer.MAX_VALUE;

    for (int pos : reach) {
      int x = pos / n;
      int y = pos % n;
      // (x,y)是所有马都可达的位置，stepMap[x][y]记录所有马到达此位置的步数和
      minStep = Math.min(minStep, stepMap[x][y]);
    }

    return minStep;
  }

  // 广搜
  public static void bfs(int sx, int sy, int k) {
    // 广搜队列
    LinkedList<int[]> queue = new LinkedList<>();
    // (sx,sy)为马所在初始位置，马到达初始位置需要0步
    queue.add(new int[] {sx, sy, 0});

    // 记录该马可以访问(sx,sy)位置
    HashSet<Integer> vis = new HashSet<>();
    vis.add(sx * n + sy); // 二维坐标一维化

    // k记录该马剩余可走步数
    while (queue.size() > 0 && k > 0) {
      // newQueue记录该马花费相同步数的可达的位置（即BFS按层遍历的层）
      LinkedList<int[]> newQueue = new LinkedList<>();

      // 按层BFS
      for (int[] tmp : queue) {
        // 当前马所在位置(x,y)，以及马到达该位置的步数step
        int x = tmp[0];
        int y = tmp[1];
        int step = tmp[2];

        for (int[] offset : offsets) {
          // 马走日到达的新位置
          int newX = x + offset[0];
          int newY = y + offset[1];

          int pos = newX * n + newY;

          // 如果新位置越界或者已访问过，则不能访问
          if (newX < 0 || newX >= m || newY < 0 || newY >= n || vis.contains(pos)) continue;

          // 将新位置加入新层
          newQueue.add(new int[] {newX, newY, step + 1});
          // 该马到达(newX, newY)位置最小步数为step+1, 由于该马首次到达(newX, newY)位置，因此step+1就是最小步数
          stepMap[newX][newY] += step + 1;
          // 记录该马访问过该位置，后续如果该马再次访问该位置，则不是最小步数
          vis.add(pos);
        }
      }

      queue = newQueue;
      k--; // 剩余步数减1
    }

    // BFS完后，将公共可达位置reach和当前马可达位置取交集，交集部分就是新的公共可达位置
    reach.retainAll(vis);
  }
}

Python算法源码

import sys

# 输入获取
m, n = map(int, input().split())  # 棋盘行数, 棋盘列数
grid = [input() for _ in range(m)]  # 棋盘矩阵
stepGrid = [[0] * n for _ in range(m)]  # 最小步数和矩阵，stepMap[i][j]记录各个马走到棋盘(i,j)位置的最小步数之和

# 记录所有马都可达的公共位置坐标
reach = set()
for i in range(m):
    for j in range(n):
        reach.add(i * n + j)

# 马走日的偏移量
offsets = ((1, 2), (1, -2), (2, 1), (2, -1), (-1, 2), (-1, -2), (-2, 1), (-2, -1))


# 广搜
def bfs(sx, sy, k):
    global reach

    # 广搜队列
    # (sx,sy)为马所在初始位置，马到达初始位置需要0步
    queue = [(sx, sy, 0)]

    # 记录该马可以访问(sx,sy)位置
    vis = set()
    vis.add(sx * n + sy)  # 二维坐标一维化

    # k记录该马剩余可走步数
    while len(queue) > 0 and k > 0:
        # newQueue记录该马花费相同步数的可达的位置（即BFS按层遍历的层）
        newQueue = []

        # 按层BFS
        for x, y, step in queue:
            for offsetX, offsetY in offsets:
                # 马走日到达的新位置
                newX = x + offsetX
                newY = y + offsetY

                pos = newX * n + newY

                # 如果新位置越界或者已访问过，则不能访问
                if newX < 0 or newX >= m or newY < 0 or newY >= n or (pos in vis):
                    continue

                # 将新位置加入新层
                newQueue.append((newX, newY, step + 1))

                # 该马到达(newX, newY)位置最小步数为step+1, 由于该马首次到达(newX, newY)位置，因此step+1就是最小步数
                stepGrid[newX][newY] += step + 1

                # 记录该马访问过该位置，后续如果该马再次访问该位置，则不是最小步数
                vis.add(pos)

        queue = newQueue
        k -= 1  # 剩余步数减1

    # BFS完后，将公共可达位置reach和当前马可达位置vis取交集，交集部分就是新的公共可达位置
    reach &= vis


# 算法入口
def getResult():
    # 遍历棋盘
    for i in range(m):
        for j in range(n):
            # 如果棋盘(i,j)位置是马
            if grid[i][j] != '.':
                # 马的等级
                k = int(grid[i][j])
                # 对该马进行BFS走日
                bfs(i, j, k)

    # 如果所有马走完，发现没有公共可达位置
    if len(reach) == 0:
        return -1

    # 记录所有马都可达位置的最小步数和
    minStep = sys.maxsize

    for pos in reach:
        x = pos // n
        y = pos % n
        # (x,y)是所有马都可达的位置，stepMap[x][y]记录所有马到达此位置的步数和
        minStep = min(minStep, stepGrid[x][y])

    return minStep


# 算法调用
print(getResult())

C算法源码

#include <stdio.h>
#include <limits.h>
#include <math.h>

#define MAX_SIZE 26

// 棋盘行数, 棋盘列数
int m, n;
// 棋盘矩阵
char map[MAX_SIZE][MAX_SIZE];
// 最小步数和矩阵，stepMap[i][j]记录各个马走到棋盘(i,j)位置的最小步数之和
int stepMap[MAX_SIZE][MAX_SIZE] = {0};

// 记录所有马都可达的公共位置坐标
int reach[MAX_SIZE * MAX_SIZE] = {0};
int reach_size = 0;

// 马走日的偏移量
int offsets[8][2] = {{1,  2},
                     {1,  -2},
                     {2,  1},
                     {2,  -1},
                     {-1, 2},
                     {-1, -2},
                     {-2, 1},
                     {-2, -1}};

// 广搜
void bfs(int sx, int sy, int k) {
    // 广搜队列
    int queue[m * n][3];
    int queue_size = 0;

    // (sx,sy)为马所在初始位置，马到达初始位置需要0步
    queue[queue_size][0] = sx;
    queue[queue_size][1] = sy;
    queue[queue_size][2] = 0;

    queue_size++;

    // 记录该马可以访问(sx,sy)位置
    int vis[MAX_SIZE * MAX_SIZE] = {0};
    vis[sx * n + sy] = 1;

    // k记录该马剩余可走步数
    while (queue_size > 0 && k > 0) {
        // newQueue记录该马花费相同步数的可达的位置（即BFS按层遍历的层）
        int newQueue[m * n][3];
        int newQueue_size = 0;

        // 按层BFS
        for (int i = 0; i < queue_size; i++) {
            // 当前马所在位置(x,y)，以及马到达该位置的步数step
            int x = queue[i][0];
            int y = queue[i][1];
            int step = queue[i][2];

            for (int j = 0; j < 8; j++) {
                // 马走日到达的新位置
                int newX = x + offsets[j][0];
                int newY = y + offsets[j][1];

                int pos = newX * n + newY;

                // 如果新位置越界或者已访问过，则不能访问
                if (newX < 0 || newX >= m || newY < 0 || newY >= n || vis[pos]) continue;

                // 将新位置加入新层
                newQueue[newQueue_size][0] = newX;
                newQueue[newQueue_size][1] = newY;
                newQueue[newQueue_size][2] = step + 1;

                newQueue_size++;

                // 该马到达(newX, newY)位置最小步数为step+1, 由于该马首次到达(newX, newY)位置，因此step+1就是最小步数
                stepMap[newX][newY] += step + 1;

                // 记录该马访问过该位置，后续如果该马再次访问该位置，则不是最小步数
                vis[pos] = 1;
            }
        }

        for (int i = 0; i < newQueue_size; i++) {
            queue[i][0] = newQueue[i][0];
            queue[i][1] = newQueue[i][1];
            queue[i][2] = newQueue[i][2];
        }
        queue_size = newQueue_size;

        k--; // 剩余步数减1
    }

    // BFS完后，将公共可达位置reach和当前马可达位置取交集，交集部分就是新的公共可达位置
    for (int i = 0; i < m * n; i++) {
        if (reach[i] == 1 && vis[i] == 0) {
            reach[i] = 0;
            reach_size--;
        }
    }
}

int getResult() {
    // 遍历棋盘
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            // 如果棋盘(i,j)位置是马
            if (map[i][j] != '.') {
                // 马的等级
                int k = map[i][j] - '0';
                // 对该马进行BFS走日
                bfs(i, j, k);
            }
        }
    }

    // 如果所有马走完，发现没有公共可达位置
    if (reach_size == 0) {
        return -1;
    }

    // 记录所有马都可达位置的最小步数和
    int minStep = INT_MAX;

    for (int i = 0; i < m * n; i++) {
        if(reach[i] != 1) continue;
        
        int x = i / n;
        int y = i % n;
        // (x,y)是所有马都可达的位置，stepMap[x][y]记录所有马到达此位置的步数和
        minStep = (int) fmin(minStep, stepMap[x][y]);
    }

    return minStep;
}

int main() {
    scanf("%d %d", &m, &n);

    for (int i = 0; i < m; i++) {
        scanf("%s", map[i]);

        for (int j = 0; j < n; j++) {
            reach[i * n + j] = 1;
        }
    }

    reach_size = m * n;

    printf("%dn", getResult());

    return 0;
}