跳马 - 华为OD统一考试（D卷）
OD统一考试（D卷）
分值： 200分
题解： Java / Python / C++
题目描述
马是象棋(包括中国象棋只和国际象棋）中的棋子，走法是每步直一格再斜一格，即先横着或直着走一格，然后再斜着走一个对角线，可进可退，可越过河界，俗称马走 “日“ 字。
给项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)，代表此格点存在等级为的“马”。
输出描述
输出最少需要的总步数 (每匹马的步数相加)，不存在则输出-1。
示例1
输入：
3 2
..
2.
..
输出：
0
示例2
输入：
3 5
47.48
4744.
7....
输出：
17
题解
这道题目通过**广度优先搜索（BFS）**来解决。首先，遍历棋盘上所有的马的位置，对每匹马进行 BFS 操作，记录其可抵达的位置马的数量和到达每个位置的最小步数。最后，找到一个位置，其可抵达的马的数量等于总马的数量，且总步数最小，输出最小步数。
以下是解题思路的主要步骤：
- 遍历棋盘，找到所有马的位置，对每个马进行 BFS 操作。
- 在 BFS 过程中，记录每个位置被多少匹马抵达，以及每个位置的总步数。
- 遍历所有位置，找到一个位置，其可抵达的马的数量等于总马的数量，且总步数最小。
这样可以得到最小的总步数，或者如果不存在满足条件的位置，则输出 -1。
下面是给定的代码解法的一些说明：
- 使用二维数组
arrive记录每个位置被多少匹马抵达。- 使用二维数组
steps记录每个位置的总步数。- 使用 BFS 进行搜索，每层搜索代表走的步数，直到达到指定的最大步数。
- 遍历所有位置，找到一个位置，其可抵达的马的数量等于总马的数量，且总步数最小。
在代码中，BFS 的过程中使用队列进行广度优先搜索，记录每个位置的状态。最后，通过遍历所有位置找到满足条件的最小总步数。
Java
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.Scanner;
/**
* @author code5bug
*/
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int m = scanner.nextInt(), n = scanner.nextInt();
scanner.nextLine();
char[][] board = new char[m][n];
for (int i = 0; i < m; i++) {
board[i] = scanner.nextLine().toCharArray();
}
// 记录棋盘上指定位置有多少匹马可以抵达当前位置
int[][] arrive = new int[m][n];
// 记录马抵达当前位置最少的总步数
int[][] steps = new int[m][n];
int horseCnt = 0;
for (int r = 0; r < m; r++) {
for (int c = 0; c < n; c++) {
if (board[r][c] != '.') {
horseCnt++;
bfs(r, c, board[r][c] - '0', arrive, steps, m, n);
}
}
}
int minSteps = Integer.MAX_VALUE;
for (int r = 0; r < m; r++) {
for (int c = 0; c < n; c++) {
if (arrive[r][c] == horseCnt) {
minSteps = Math.min(minSteps, steps[r][c]);
}
}
}
System.out.println((minSteps != Integer.MAX_VALUE) ? minSteps : -1);
}
private static void bfs(int startRow, int startCol, int leftStep, int[][] arrive, int[][] steps, int m, int n) {
int[][] directions = {{1, 2}, {2, 1}, {-1, 2}, {-2, 1}, {1, -2}, {2, -1}, {-1, -2}, {-2, -1}};
boolean[][] visited = new boolean[m][n];
Queue<int[]> queue = new ArrayDeque<>();
queue.offer(new int[]{startRow, startCol});
int step = 0;
while (step <= leftStep) {
int size = queue.size();
for (int i = 0; i < size; i++) {
int[] current = queue.poll();
int row = current[0], col = current[1];
if (visited[row][col]) continue;
visited[row][col] = true;
arrive[row][col]++;
steps[row][col] += step;
for (int[] direction : directions) {
int newRow = row + direction[0];
int newCol = col + direction[1];
if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n && !visited[newRow][newCol]) {
queue.offer(new int[]{newRow, newCol});
}
}
}
step++;
}
}
}
Python
from collections import deque
from math import inf
m, n = map(int, input().split())
board = list([input() for _ in range(m)])
# 记录棋盘上指定位置有多少匹马可以抵达当前位置
arrive = [[0] * n for _ in range(m)]
# 记录马抵达当前位置最少的总步数
steps = [[0] * n for _ in range(m)]
def bfs(r: int, c: int, left_step: int):
"""
马从（r,c）出发，最多走 left_step 步，
1、 更新此马到达棋盘其他位置最少需要的步数（累计到 steps 中）；
2、 更新此马能否到达棋盘其他位置，位置可以到达则arrive中指定位置的马可抵达数量 + 1；
"""
global arrive, steps, m, n
vis = [[False] * n for _ in range(m)]
q = deque()
q.append((r, c))
step = 0
while step <= left_step:
size = len(q)
for _ in range(size):
row, col = q.popleft()
if vis[row][col]: # 已经到达过
continue
# 第一次到达
vis[row][col] = True
arrive[row][col] += 1
steps[row][col] += step
# 下一步可以抵达的路径
for dx in (1, 2, -1, -2):
for dy in (1, 2, -1, -2):
if abs(dx * dy) != 2: # 非法的走法
continue
nrow, ncol = row + dx, col + dy
if 0 <= nrow < m and 0 <= ncol < n and not vis[nrow][ncol]:
q.append((nrow, ncol))
step += 1
horse_cnt = 0
for r, row in enumerate(board):
for c, val in enumerate(row):
if val != '.':
horse_cnt += 1
bfs(r, c, int(val))
min_steps = inf
for r in range(m):
for c in range(n):
if arrive[r][c] == horse_cnt:
min_steps = min(min_steps, steps[r][c])
print(min_steps if min_steps != inf else -1)
C++
#include <iostream>
#include <vector>
#include <deque>
using namespace std;
int m, n;
vector<string> board;
vector<vector<int>> arrive;
vector<vector<int>> steps;
void bfs(int r, int c, int left_step) {
vector<vector<bool>> vis(m, vector<bool>(n, false));
deque<pair<int, int>> q;
q.push_back({r, c});
int step = 0;
while (step <= left_step) {
int size = q.size();
for (int i = 0; i < size; ++i) {
int row = q.front().first;
int col = q.front().second;
q.pop_front();
if (vis[row][col]) {
continue;
}
vis[row][col] = true;
arrive[row][col] += 1;
steps[row][col] += step;
int dx[] = {1, 2, -1, -2};
int dy[] = {1, 2, -1, -2};
for (int drow : dx) {
for (int dcol : dy) {
if (abs(drow * dcol) != 2) {
continue;
}
int nrow = row + drow;
int ncol = col + dcol;
if (0 <= nrow && nrow < m && 0 <= ncol && ncol < n && !vis[nrow][ncol]) {
q.push_back({nrow, ncol});
}
}
}
}
step += 1;
}
}
int main() {
cin >> m >> n;
board.resize(m);
arrive.assign(m, vector<int>(n, 0));
steps.assign(m, vector<int>(n, 0));
for (int i = 0; i < m; ++i) {
cin >> board[i];
}
int horse_cnt = 0;
for (int r = 0; r < m; ++r) {
for (int c = 0; c < n; ++c) {
if (board[r][c] != '.') {
horse_cnt += 1;
bfs(r, c, board[r][c] - '0');
}
}
}
int min_steps = INT_MAX;
for (int r = 0; r < m; ++r) {
for (int c = 0; c < n; ++c) {
if (arrive[r][c] == horse_cnt) {
min_steps = min(min_steps, steps[r][c]);
}
}
}
cout << (min_steps != INT_MAX ? min_steps : -1) << endl;
return 0;
}
🙏整理题解不易， 如果有帮助到您，请给点个赞 ❤️ 和收藏 ⭐，让更多的人看到。🙏🙏🙏
#面经##春招##秋招##校招##华为#
