一. 题目
马是象棋(包括中国象棋和国际象棋)中的棋子，走法是每步直一格再斜一格，即先横着或直着走一格，然后再斜着走一个对角线，可进可退，可越过河界，俗称“马走‘日’字。
给顶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。
补充说明：
示例1
输入：
3 2
…
2.
…
输出：
0
说明：
只有一匹马，不需要跳动
示例2
输入：
3 5
47.48
4744.
7…
输出：
17
二.解题思路
-
对于每匹马，我们需要找到它们能够共同到达的位置。为了达到这个目的，可以使用深度优先搜索（DFS）或广度优先搜索（BFS）来遍历所有可能的位置。
-
对于每匹马，从它当前的位置出发，按照马的走法，计算它能够到达的所有位置，并标记这些位置。可以使用一个二维数组来表示标记，例如
visited数组。 -
为了避免不同马之间的冲突，每匹马的标记不同。可以使用一个变量来表示当前马的标记值，每次遍历新的马时，增加标记值。
-
统计每匹马到达的位置需要的步数，累加得到最终结果。
-
如果存在某个位置被所有马都标记到，说明它是一个可以共同到达的位置，返回步数之和；否则，返回-1表示无法找到共同到达的位置。
以上是一个大致的解题思路，具体实现时需要考虑细节，例如遍历时的边界条件、标记的方式等。可以根据这个思路编写代码。
三.题解代码
Python题解代码
def min_steps(m, n, grid):
positions = []
for i in range(m):
for j in range(n):
if grid[i][j] != '.':
positions.append((i, j))
def distance(p1, p2):
return max(abs(p1[0] - p2[0]), abs(p1[1] - p2[1]))
min_total_steps = float('inf')
for pos in positions:
total_steps = 0
for other_pos in positions:
if pos != other_pos:
total_steps += distance(pos, other_pos)
min_total_steps = min(min_total_steps, total_steps)
return min_total_steps if min_total_steps != float('inf') else -1
m, n = map(int, input().split())
grid = [input() for _ in range(m)]
print(min_steps(m, n, grid))
JAVA题解代码
import java.util.Scanner;
import java.util.*;
import java.util.stream.Stream;
import java.util.HashMap;
import java.util.regex.Matcher;
import java.util.regex.Pattern;
import java.util.stream.Collectors;
public class Main {
public static int m;
public static int n;
public static int[][] matrix;
public static int[][] result;
public static int[][] directions = {{2, 1}, {2, -1}, {-2, 1}, {-2, -1},{1, 2}, {1, -2}, {-1, 2}, {-1, -2}};
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
m = in.nextInt();
n = in.nextInt();
in.nextLine();
result = new int[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
result[i][j] = 0;
}
}
matrix = new int[m][n];
for (int i = 0; i < m; i++) {
String[] inputs = in.nextLine().split(" ");
for (int j = 0; j < n; j++) {
if(!inputs[j].equals(".")){
clear_matrix();
bfs(i, j, Integer.parseInt(inputs[j]));
update_result();
}
}
}
int output = Integer.MAX_VALUE;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if(result[i][j]!=-1){
output = output>result[i][j] ? result[i][j] : output;
} else {
continue;
}
}
}
if(output == Integer.MAX_VALUE){
System.out.println(0);
} else {
System.out.println(output);
}
}
public static void clear_matrix() {
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
matrix[i][j] = -1;
}
}
}
public static void update_result() {
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (matrix[i][j] == -1) {
result[i][j] = -1;
} else if(result[i][j] == -1){
result[i][j] = -1;
} else {
result[i][j] += matrix[i][j];
}
}
}
}
public static void bfs(int i, int j, int step) {
matrix[i][j] = 0;
Queue<int[]> queue = new LinkedList<>();
queue.add(new int[]{i, j});
int index = 1;
while(true){
if(queue.isEmpty() || index>step){
break;
} else {
int size = queue.size();
for (int k = 0; k < size; k++) {
int[] current = queue.poll();
for (int l=0; l<8; l++) {
int next_i = current[0] + directions[l][0];
int next_j = current[1] + directions[l][1];
if (0 <= next_i && next_i < m && 0 <= next_j
&& next_j < n && matrix[next_i][next_j] == -1) {
matrix[next_i][next_j] = index;
queue.add(new int[] {next_i, next_j});
}
}
}
}
index+=1;
}
}
}
C/C++题解代码
#include <iostream>
#include <vector>
#include <queue>
#include <string>
using namespace std;
const int dx[] = {1, 1, 2, 2, -1, -1, -2, -2};
const int dy[] = {2, -2, 1, -1, 2, -2, 1, -1};
bool isValid(int x, int y, int m, int n) {
return x >= 0 && x < m && y >= 0 && y < n;
}
int minSteps(int m, int n, vector<string>& board) {
vector<pair<int, int>> horses;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (isdigit(board[i][j])) {
horses.push_back({i, j});
}
}
}
int totalSteps = 0;
for (auto& horse : horses) {
int x = horse.first;
int y = horse.second;
int k = board[x][y] - '0';
vector<vector<bool>> visited(m, vector<bool>(n, false));
queue<pair<int, int>> q;
q.push({x, y});
visited[x][y] = true;
int steps = 0;
while (!q.empty()) {
int size = q.size();
for (int i = 0; i < size; ++i) {
auto [curX, curY] = q.front();
q.pop();
if (steps > k) {
break;
}
for (int j = 0; j < 8; ++j) {
int newX = curX + dx[j];
int newY = curY + dy[j];
if (isValid(newX, newY, m, n) && !visited[newX][newY]) {
if (board[newX][newY] == '.') {
visited[newX][newY] = true;
q.push({newX, newY});
} else if (board[newX][newY] == to_string(k)) {
totalSteps += steps + 1;
goto nextHorse;
}
}
}
}
++steps;
}
totalSteps = -1;
break;
nextHorse:;
}
return totalSteps;
}
int main() {
int m, n;
cin >> m >> n;
vector<string> board(m, string(n, ' '));
for (int i = 0; i < m; ++i) {
cin >> board[i];
}
cout << minSteps(m, n, board) << endl;
return 0;
}
JS题解代码
const readline = require('readline');
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout
});
let n, m, dx, dy, dist, g = [], pos = [];
// 广度优先搜索函数，用于计算从马的当前位置出发到达(i, j)的最短距离
function bfs(x, y, u, k) {
const queue = [];
queue.push([x, y]);
dist[u][x][y] = 0;
while (queue.length > 0) {
const [x1, y1] = queue.shift();
// 遍历八个方向
for (let i = 0; i < 8; i++) {
const x2 = x1 + dx[i];
const y2 = y1 + dy[i];
// 检查新位置是否在棋盘内，是否满足条件
if (x2 >= 0 && x2 < n && y2 >= 0 && y2 < m &&
dist[u][x2][y2] > dist[u][x1][y1] + 1 &&
dist[u][x1][y1] < k) {
// 更新最短距离，并将新位置加入队列
dist[u][x2][y2] = dist[u][x1][y1] + 1;
queue.push([x2, y2]);
}
}
}
}
rl.on('line', (line) => {
const lines = line.trim().split(' ');
if (!n) {
// 读取第一行输入，初始化变量
n = parseInt(lines[0]);
m = parseInt(lines[1]);
dx = [1, 1, -1, -1, 2, 2, -2, -2];
dy = [-2, 2, -2, 2, -1, 1, -1, 1];
dist = {};
} else {
// 读取棋盘每一行的输入
const row = line.split('');
const i = g.length;
g.push(row);
for (let j = 0; j < m; j++) {
const u = i * m + j;
// 初始化每个马到所有位置的最短距离
dist[u] = Array.from({ length: n }, () => Array(m).fill(0x3f3f3f3f));
if ('1' <= row[j] && row[j] <= '9') {
// 如果当前位置有马，则进行广度优先搜索
bfs(i, j, u, parseInt(row[j]));
pos.push([i, j]); // 记录马的位置
}
}
}
}).on('close', () => {
// 计算所有可能的马的位置到每个空白格的最短距离和
let ans = 0x3f3f3f3f;
for (let i = 0; i < n; i++) {
for (let j = 0; j < m; j++) {
let cnt = 0;
for (const p of pos) {
const u = p[0] * m + p[1];
if (dist[u][i][j] === 0x3f3f3f3f) {
cnt = 0x3f3f3f3f;
break;
}
cnt += dist[u][i][j];
}
ans = Math.min(ans, cnt);
}
}
// 输出结果
if (ans === 0x3f3f3f3f) {
console.log("-1");
} else {
console.log(ans);
}
});
四.代码讲解(Java&Python&C++&JS分别讲解)
Python题解代码解析：
-
函数定义：
min_steps函数接收三个参数，分别是棋盘的行数m，列数n，以及棋盘的状态grid。 -
初始化： 在函数内部，首先定义了一个空列表
positions用于存储每匹马的位置。 -
遍历棋盘： 使用两层循环遍历整个棋盘，如果某个位置上有马（不是空格
.），则将其坐标加入positions列表。 -
计算最小总步数： 遍历每匹马的位置，对于每匹马，再次遍历所有马的位置，计算该马到其他马的最小步数之和。更新最小总步数。
-
返回结果： 如果最小总步数不是正无穷，说明存在共同到达的位置，返回最小总步数；否则，返回 -1。
-
输入处理： 最后，从输入中读取棋盘的行数、列数以及棋盘状态，并调用
min_steps函数输出结果。
JAVA题解代码解析：
-
导入库： 导入需要使用的 Java 库，包括 Scanner 类和相关的集合类。
-
全局变量定义： 定义了全局变量
m、n、matrix、result和directions。其中，matrix用于记录每个位置到达目标位置的步数，result用于记录每个位置所有马到达的最小步数之和，directions定义了马的八个可能的移动方向。 -
主函数：
main函数接收输入，初始化各个数组，然后通过两层循环遍历输入的棋盘。 -
清空和更新操作： 在循环中，对于每个非空格的位置，进行了
clear_matrix和bfs操作。clear_matrix用于清空matrix数组，bfs用于进行广度优先搜索，计算每个位置到达目标位置的最小步数。 -
计算最终结果： 循环结束后，通过
update_result函数更新result数组，计算每个位置所有马到达的最小步数之和。然后，找到result数组中的最小值，并输出结果。
C/C++题解代码解析：
-
头文件和命名空间： 包含了必要的头文件，使用了
std命名空间。 -
函数定义：
isValid函数用于检查坐标是否在棋盘内；minSteps函数用于计算最小步数。 -
全局变量定义： 定义了一些常量和全局变量，包括马的八个可能的移动方向。
-
主函数：
main函数读取输入，初始化棋盘，调用minSteps函数计算最小步数，并输出结果。 -
isValid 函数： 用于检查坐标是否在棋盘内。
-
minSteps 函数： 遍历棋盘，找到所有马的位置，然后对每匹马，使用广度优先搜索计算到达其他位置的最小步数。
-
输出结果： 输出最终的最小步数，如果无法找到共同到达的位置则输出 -1。
JS题解代码解析：
-
模块导入和全局变量定义： 使用
readline模块进行输入输出，定义了一些常量和全局变量。 -
bfs 函数： 广度优先搜索函数，用于计算从当前马的位置出发到达目标位置的最短距离。
-
输入处理： 使用
readline逐行读取输入，根据输入初始化棋盘和其他相关信息。 -
bfs 函数实现： 对于每匹马，使用广度优先搜索计算到达其他位置的最小步数。
-
计算最终结果： 遍历棋盘的每个空白格，计算所有马到达该位置的最小步数和，找到最小值，输出结果。
-
输出结果： 输出最终的最小步数，如果无法找到共同到达的位置则输出 -1。
这些代码实现了同一个问题的解决方案，使用了不同的编程语言。它们的基本思路相似，都是通过遍历马的位置，使用广度优先搜索等方法计算最小步数。