E卷-跳马(200分)

跳马

问题描述

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

"马"的走法如下：从坐标 $(x,y)$ 出发，一步可以到达以下 8 个位置之一： $(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$ ，表示棋盘的行数和列数。 $(1 \leq m, n \leq 25)$

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

输出格式

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

样例输入

3 2
. .
2 .
. .

样例输出

样例解释

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

样例输入

样例输出

数据范围

$1 \leq m, n \leq 25$
马的等级 $k$ 满足 $1 \leq k \leq 9$

题解

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

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

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

步数记录：使用二维数组 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()

#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", get_result(m, n, board));

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

    return 0;
}

Javascript

const readline = require('readline');

const MAX_SIZE = 26;
const offsets = [[1, 2], [1, -2], [2, 1], [2, -1], [-1, 2], [-1, -2], [-2, 1], [-2, -1]];

function bfs(sx, sy, k, m, n, stepMap, reach) {
    const queue = [[sx, sy, 0]];
    const vis = new Set([`${sx},${sy}`]);

    // BFS主循环
    while (queue.length > 0 && k > 0) {
        const newQueue = [];
        for (const [x, y, step] of queue) {
            for (const [dx, dy] of offsets) {
                const newX = x + dx;
                const newY = y + dy;
                const key = `${newX},${newY}`;
                // 检查新位置是否有效且未访问
                if (newX >= 0 && newX < m && newY >= 0 && newY < n && !vis.has(key)) {
                    newQueue.push([newX, newY, step + 1]);
                    stepMap[newX][newY] += step + 1;
                    vis.add(key);
                }
            }
        }
        queue.length = 0;
        queue.push(...newQueue);
        k--;
    }

    // 更新可达性
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            reach[i][j] = reach[i][j] && vis.has(`${i},${j}`);
        }
    }
}

function getResult(m, n, board) {
    // 初始化步数图和可达性数组
    const stepMap = Array.from({ length: m }, () => Array(n).fill(0));
    const reach = Array.from({ length: m }, () => Array(n).fill(true));

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

    // 寻找最小步数
    let minStep = Infinity;
    let hasCommon = false;
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (reach[i][j]) {
                hasCommon = true;
                minStep = Math.min(minStep, stepMap[i][j]);
            }
        }
    }

    return hasCommon ? minStep : -1;
}

const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

let m, n;
const board = [];

rl.on('line', (line) => {
    if (!m) {
        // 读取棋盘大小
        [m, n] = line.split(' ').map(Number);
    } else {
        // 读取棋盘内容
        board.push(line.split(' '));
        if (board.length === m) {
            // 输出结果
            console.log(getResult(m, n, board));
            rl.close();
        }
    }
});

Java

import java.util.*;

public class Main {
    private static final int MAX_SIZE = 26;
    // 马走日的八个方向偏移量
    private static final int[][] offsets = {{1, 2}, {1, -2}, {2, 1}, {2, -1}, {-1, 2}, {-1, -2}, {-2, 1}, {-2, -1}};

    // 广度优先搜索函数
    private static void bfs(int sx, int sy, int k, int m, int n, int[][] stepMap, boolean[][] reach) {
        Queue<int[]> queue = new LinkedList<>();
        boolean[][] vis = new boolean[m][n];

        // 将起始点加入队列
        queue.offer(new int[]{sx, sy, 0});
        vis[sx][sy] = true;

        // BFS主循环
        while (!queue.isEmpty() && k > 0) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int[] curr = queue.poll();
                for (int[] offset : offsets) {
                    int newX = curr[0] + offset[0];
                    int newY = curr[1] + offset[1];
                    // 检查新位置是否在棋盘内且未访问过
                    if (newX >= 0 && newX < m && newY >= 0 && newY < n && !vis[newX][newY]) {
                        queue.offer(new int[]{newX, newY, curr[2] + 1});
                        stepMap[newX][newY] += curr[2] + 1;
                        vis[newX][newY] = true;
                    }
                }
            }
            k--; // 减少剩余步数
        }

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

    // 获取结果的主函数
    private static int getResult(int m, int n, char[][] board) {
        int[][] stepMap = new int[m][n];
        boolean[][] reach = new boolean[m][n];
        for (boolean[] row : reach) {
            Arrays.fill(row, true);
        }

        // 对每个马进行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, stepMap, reach);
                }
            }
        }

        // 寻找最小步数
        int minStep = Integer.MAX_VALUE;
        boolean hasCommon = false;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (reach[i][j]) {
                    hasCommon = true;
                    minStep = Math.min(minStep, stepMap[i][j]);
                }
            }
        }

        return hasCommon ? minStep : -1;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int m = scanner.nextInt();
        int n = scanner.nextInt();
        char[][] board = new char[m][n];
        
        // 读取棋盘
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                board[i][j] = scanner.next().charAt(0);
            }
        }

        // 输出结果
        System.out.println(getResult(m, n, board));
    }
}

#include <bits/stdc++.h>

const int MAX_SIZE = 26;
// 马走日的八个方向偏移量
const std::vector<std::pair<int, int>> offsets = {{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, std::vector<std::vector<int>>& step_map, std::vector<std::vector<int>>& reach) {
    std::queue<std::tuple<int, int, int>> q;
    std::vector<std::vector<int>> vis(m, std::vector<int>(n, 0));

    // 将起始点加入队列
    q.push({sx, sy, 0});
    vis[sx][sy] = true;

    // BFS主循环
    while (!q.empty() && k > 0) {
        int size = q.size();
        for (int i = 0; i < size; ++i) {
            auto [x, y, step] = q.front();
            q.pop();
            for (const auto& [dx, dy] : offsets) {
                int new_x = x + dx, new_y = y + dy;
                // 检查新位置是否在棋盘内且未访问过
                if (new_x >= 0 && new_x < m && new_y >= 0 && new_y < n && !vis[new_x][new_y]) {
                    q.push({new_x, new_y, step + 1});
                    step_map[new_x][new_y] += step + 1;
                    vis[new_x][new_y] = true;
                }
            }
        }
        --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, const std::vector<std::vector<char>>& board) {
    std::vector<std::vector<int>> step_map(m, std::vector<int>(n, 0));
    std::vector<std::vector<int>> reach(m, std::vector<int>(n, 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;
    bool has_common = false;
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            if (reach[i][j]) {
                has_common = true;
                min_step = std::min(min_step, step_map[i][j]);
            }
        }
    }

    return has_common ? min_step : -1;
}

int main() {
    int m, n;
    std::cin >> m >> n;
    std::vector<std::vector<char>> board(m, std::vector<char>(n));

    // 读取棋盘
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            std::cin >> board[i][j];
        }
    }

    // 输出结果
    std::cout << get_result(m, n, board) << std::endl;
    return 0;
}

#OD##机考##E#

OD刷题笔记文章被收录于专栏

本专栏收集并整理了一些刷题笔记