E卷-跳马(200分)

跳马

问题描述

在一个 行 列的棋盘上，分布着若干等级不同的"马"棋子。每个"马"棋子的走法类似于象棋中的马，但它们可以走 1 到 步，其中 是该马的等级。现在的任务是将所有的马移动到同一个位置，如果可能的话，需要计算出最少需要的总步数。如果不可能，则输出 -1。

"马"的走法如下：从坐标 出发，一步可以到达以下 8 个位置之一：、、、、、、、。

注意：

1. 马可以跳过其他棋子。
2. 马不能移动到棋盘外。
3. 多个马可以同时占据同一个位置。

输入格式

第一行包含两个整数 和 ，表示棋盘的行数和列数。

接下来 行，每行包含 个字符。每个字符要么是 '.'（表示该位置没有棋子），要么是 1 到 9 之间的数字（表示该位置有一个等级为该数字的马）。

输出格式

输出一个整数，表示将所有马移动到同一位置所需的最少总步数。如果无法做到，则输出 -1。

样例输入

3 2
. .
2 .
. .

样例输出

0

样例解释

棋盘上只有一匹马，它已经在一个位置上，不需要移动。

样例输入

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

样例输出

17

数据范围

• 
• 马的等级 满足

题解

这道题目是一个变种的多源最短路径问题。主要难点在于：

1. 每个"马"的移动能力不同（由其等级 决定）
2. 需要找到所有马都能到达的位置中，总步数最小的那个

多源 BFS：对棋盘上的每个马进行广度优先搜索（BFS）BFS 保证找到最短路径每个马的搜索深度受其等级 限制

步数记录：使用二维数组 stepMap[m][n] 记录所有马到达每个位置的总步数

可达性记录：使用二维布尔数组 reach[m][n] 记录每个位置是否能被所有马到达

BFS 过程：更新 stepMap：累加每个马到达各位置的步数更新 reach：取所有马可达性的交集

结果计算：遍历 reach 数组，检查是否存在公共可达点在公共可达点中找出 stepMap 值最小的，即为答案如果没有公共可达点，返回 -1

• Python

from collections import deque
import sys

MAX_SIZE = 26

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

def bfs(sx, sy, k, m, n, step_map, reach):
    # 初始化队列和访问集合
    queue = deque([(sx, sy, 0)])
    vis = set([(sx, sy)])

    # BFS主循环
    while queue and k > 0:
        new_queue = []
        for x, y, step in queue:
            for dx, dy in offsets:
                new_x, new_y = x + dx, y + dy
                # 检查新位置是否有效且未访问
                if 0 <= new_x < m and 0 <= new_y < n and (new_x, new_y) not in vis:
                    new_queue.append((new_x, new_y, step + 1))
                    step_map[new_x][new_y] += step + 1
                    vis.add((new_x, new_y))
        queue = new_queue
        k -= 1

    # 更新可达性
    reach &= vis

def get_result(m, n, board):
    # 初始化步数图和可达性集合
    step_map = [[0] * n for _ in range(m)]
    reach = set((i, j) for i in range(m) for j in range(n))

    # 对每个马进行BFS
    for i in range(m):
        for j in range(n):
            if board[i][j] != '.':
                k = int(board[i][j])
                bfs(i, j, k, m, n, step_map, reach)

    # 如果没有公共可达点,返回-1
    if not reach:
        return -1

    # 返回最小步数
    return min(step_map[x][y] for x, y in reach)

def main():
    # 读取输入
    m, n = map(int, input().split())
    board = [input().split() for _ in range(m)]
    # 输出结果
    print(get_result(m, n, board))

if __name__ == "__main__":
    main()

• C

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

#define MAX_SIZE 26

// 马走日的八个方向偏移量
const 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 m, int n, int **step_map, int **reach) {
    int vis[MAX_SIZE][MAX_SIZE] = {0};
    int queue[MAX_SIZE * MAX_SIZE][3];
    int front = 0, rear = 0;

    // 将起始点加入队列
    queue[rear][0] = sx;
    queue[rear][1] = sy;
    queue[rear][2] = 0;
    rear++;
    vis[sx][sy] = 1;

    // BFS主循环
    while (front < rear && k > 0) {
        int size = rear - front;
        for (int i = 0; i < size; ++i) {
            int x = queue[front][0];
            int y = queue[front][1];
            int step = queue[front][2];
            front++;
            for (int j = 0; j < 8; ++j) {
                int new_x = x + offsets[j][0];
                int new_y = y + offsets[j][1];
                // 检查新位置是否在棋盘内且未访问过
                if (new_x >= 0 && new_x < m && new_y >= 0 && new_y < n && !vis[new_x][new_y]) {
                    queue[rear][0] = new_x;
                    queue[rear][1] = new_y;
                    queue[rear][2] = step + 1;
                    rear++;
                    step_map[new_x][new_y] += step + 1;
                    vis[new_x][new_y] = 1;
                }
            }
        }
        --k; // 减少剩余步数
    }

    // 更新可达性
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            reach[i][j] &= vis[i][j];
        }
    }
}

// 获取结果的主函数
int get_result(int m, int n, char **board) {
    int **step_map = (int **)malloc(m * sizeof(int *));
    int **reach = (int **)malloc(m * sizeof(int *));
    for (int i = 0; i < m; ++i) {
        step_map[i] = (int *)calloc(n, sizeof(int));
        reach[i] = (int *)malloc(n * sizeof(int));
        for (int j = 0; j < n; ++j) {
            reach[i][j] = 1;
        }
    }

    // 对每个马进行BFS
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            if (board[i][j] != '.') {
                int k = board[i][j] - '0';
                bfs(i, j, k, m, n, step_map, reach);
            }
        }
    }

    // 寻找最小步数
    int min_step = INT_MAX;
    int has_common = 0;
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            if (reach[i][j]) {
                has_common = 1;
                if (step_map[i][j] < min_step) {
                    min_step = step_map[i][j];
                }
            }
        }
    }

    // 释放内存
    for (int i = 0; i < m; ++i) {
        free(step_map[i]);
        free(reach[i]);
    }
    free(step_map);
    free(reach);

    return has_common ? min_step : -1;
}

int main() {
    int m, n;
    scanf("%d %d", &m, &n);
    char **board = (char **)malloc(m * sizeof(char *));
    for (int i = 0; i < m; ++i) {
        board[i] = (char *)malloc(n * sizeof(char));
        for (int j = 0; j < n; ++j) {
            scanf(" %c", &board[i][j]);
        }
    }

    // 输出结果
    printf("%d\n",