E卷-跳马(200分)
跳马
问题描述
在一个 行 列的棋盘上,分布着若干等级不同的"马"棋子。每个"马"棋子的走法类似于象棋中的马,但它们可以走 1 到 步,其中 是该马的等级。现在的任务是将所有的马移动到同一个位置,如果可能的话,需要计算出最少需要的总步数。如果不可能,则输出 -1。
"马"的走法如下:从坐标 出发,一步可以到达以下 8 个位置之一:、、、、、、、。
注意:
- 马可以跳过其他棋子。
- 马不能移动到棋盘外。
- 多个马可以同时占据同一个位置。
输入格式
第一行包含两个整数 和 ,表示棋盘的行数和列数。
接下来 行,每行包含 个字符。每个字符要么是 '.'(表示该位置没有棋子),要么是 1 到 9 之间的数字(表示该位置有一个等级为该数字的马)。
输出格式
输出一个整数,表示将所有马移动到同一位置所需的最少总步数。如果无法做到,则输出 -1。
样例输入
3 2
. .
2 .
. .
样例输出
0
样例解释
棋盘上只有一匹马,它已经在一个位置上,不需要移动。
样例输入
3 5
4 7 . 4 8
4 7 4 4 .
7 . . . .
样例输出
17
数据范围
- 马的等级 满足
题解
这道题目是一个变种的多源最短路径问题。主要难点在于:
- 每个"马"的移动能力不同(由其等级 决定)
- 需要找到所有马都能到达的位置中,总步数最小的那个
多源 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", 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));
}
}
- Cpp
#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#本专栏收集并整理了一些刷题笔记