返回目录

题目描述

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

给定 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，stepMapi表示所有能跳到(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，之后：

• stepMapnewX += step + 1
• vis.add(newX * n + newY)

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

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

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

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

Python算法源码

from collections import deque

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

def bfs(sx, sy, k, m, n, map, reach, stepMap):
    queue = deque([(sx, sy, 0)])  # 广搜队列，初始位置以及步数
    vis = set([(sx, sy)])  # 记录已访问过的位置

    while queue and k > 0:
        newQueue = deque()  # 新的队列

        # 按层BFS
        for x, y, step in queue:
            for dx, dy in offsets:
                newX, newY = x + dx, y + dy

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

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

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

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

def get_result(m, n, map):
    # 最小步数和矩阵，stepMap[i][j]记录各个马走到棋盘(i,j)位置的最小步数之和
    stepMap = [[0] * n for _ in range(m)]
    # 记录所有马都可达的公共位置坐标
    reach = set((i, j) for i in range(m) for j in range(n))
  
    # 遍历棋盘
    for i in range(m):
        for j in range(n):
            # 如果棋盘(i,j)位置是马
            if map[i][j] != '.':
                # 马的等级
                k = int(map[i][j])
                # 对该马进行BFS走日
                bfs(i, j, k, m, n, map, reach, stepMap)

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

    # 记录所有马都可达位置的最小步数和
    minStep = float('inf')

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

    return minStep

if __name__ == "__main__":
    # 棋盘行数和列数
    m, n = map(int, input().split())
    # 棋盘矩阵
    map = [input() for _ in range(m)]

    result = get_result(m, n, map)
    print(result)

C算法源码

#include <stdio.h>
#include <stdbool.h>

#define MAX_M 100
#define MAX_N 100

// 棋盘行数
int m;
// 棋盘列数
int n;
// 棋盘矩阵
char map[MAX_M][MAX_N];
// 最小步数和矩阵，stepMap[i][j]记录各个马走到棋盘(i,j)位置的最小步数之和
int stepMap[MAX_M][MAX_N];
// 记录所有马都可达的公共位置坐标
bool reach[MAX_M * MAX_N];

// 马走日的偏移量
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[MAX_M * MAX_N][3];
    int front = 0, rear = 0;
    // (sx,sy)为马所在初始位置，马到达初始位置需要0步
    queue[rear][0] = sx;
    queue[rear][1] = sy;
    queue[rear][2] = 0;
    rear++;

    // 记录该马可以访问(sx,sy)位置
    bool vis[MAX_M * MAX_N] = {false};
    vis[sx * n + sy] = true; // 二维坐标一维化

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

        // 按层BFS
        for (int i = front; i < rear; 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[newRear][0] = newX;
                newQueue[newRear][1] = newY;
                newQueue[newRear][2] = step + 1;
                newRear++;
                // 该马到达(newX, newY)位置最小步数为step+1, 由于该马首次到达(newX, newY)位置，因此step+1就是最小步数
                stepMap[newX][newY] += step + 1;
                // 记录该马访问过该位置，后续如果该马再次访问该位置，则不是最小步数
                vis[pos] = true;
            }
        }

        front = rear;
        rear = newRear;
        k--; // 剩余步数减1
    }

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

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

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

    // 初始化
    for (int i = 0; i < m * n; i++) {
        reach[i] = true;
    }

    // 遍历棋盘
    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);
            }
        }
    }

    // 如果所有马走完，发现没有公共可达位置
    bool noCommonReach = true;
    for (int i = 0; i < m * n; i++) {
        if (reach[i]) {
            noCommonReach = false;
            break;
        }
    }

    if (noCommonReach) {
        printf("-1\n");
        return 0;
    }

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

    printf("%d\n", minStep);

    return 0;
}

Java算法源码

import java.util.*;

public class Main {
    static int m, n;
    static char[][] grid;
    static int[][] stepGrid;
    static Set<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 scanner = new Scanner(System.in);
        m = scanner.nextInt();
        n = scanner.nextInt();
        grid = new char[m][n];
        stepGrid = new int[m][n];
        reach = new HashSet<>();

        for (int i = 0; i < m; i++) {
            grid[i] = scanner.next().toCharArray();
        }

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                reach.add(i * n + j);
            }
        }

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] != '.') {
                    int k = grid[i][j] - '0';
                    bfs(i, j, k);
                }
            }
        }

        if (reach.size() == 0) {
            System.out.println(-1);
        } else {
            int minStep = Integer.MAX_VALUE;
            for (int pos : reach) {
                int x = pos / n;
                int y = pos % n;
                minStep = Math.min(minStep, stepGrid[x][y]);
            }
            System.out.println(minStep);
        }
    }

    static void bfs(int sx, int sy, int k) {
        Queue<int[]> queue = new LinkedList<>();
        Set<Integer> vis = new HashSet<>();
        queue.offer(new int[]{sx, sy, 0});
        vis.add(sx * n + sy);

        while (!queue.isEmpty() && k > 0) {
            Queue<int[]> newQueue = new LinkedList<>();
            while (!queue.isEmpty()) {
                int[] cur = queue.poll();
                int x = cur[0];
                int y = cur[1];
                int step = cur[2];
                for (int[] offset : offsets) {
                    int offsetX = offset[0];
                    int offsetY = offset[1];
                    int newX = x + offsetX;
                    int newY = y + offsetY;
                    int pos = newX * n + newY;
                    if (newX < 0 || newX >= m || newY < 0 || newY >= n || vis.contains(pos)) {
                        continue;
                    }
                    newQueue.offer(new int[]{newX, newY, step + 1});
                    stepGrid[newX][newY] += step + 1;
                    vis.add(pos);
                }
            }
            queue = newQueue;
            k--;
        }
        reach.retainAll(vis);
    }
}