20天拿下华为OD笔试之【BFS】2025C-跳马问题【Py/Java/C++/C/JS/Go六种语言OD独家2025C卷真题】【欧弟算法】全网注释最详细分类最全的华子OD真题题解
可上 欧弟OJ系统 练习华子OD、大厂真题
绿色聊天软件戳od1441了解算法冲刺训练(备注【CSDN】否则不通过)
文章目录
相关推荐阅读
- 【华为OD机考】2025C+2025B+2024E+D卷真题【完全原创题解 | 详细考点分类 | 不断更新题目】
- 【华为OD笔试】2025C+2025B+2024E+D卷真题机考套题汇总【真实反馈,不断更新,限时免费】
- 【华为OD笔试】2024E+D卷命题规律解读【分析500+场OD笔试考点总结】
- 【华为OD流程】性格测试选项+注意事项】
题目练习网址:【BFS】2025C-跳马问题
题目描述与示例
题目描述
输入 m 和 n 两个数,m 和 n 表示一个 m*n 的棋盘。输入棋盘内的数据。棋盘中存在数字和"."两种字符,如果是数字表示该位置是一匹马,如果是"."表示该位置为空的,棋盘内的数字表示为该马能走的最大步数。
例如棋盘内某个位置一个数字为 k,表示该马只能移动 0~k 步的距离。
棋盘内的马移动类似于中国象棋中的马移动,先在水平或者垂直方向上移动一格,然后再将其移动到对角线位置。
棋盘内的马可以移动到同一个位置,同一个位置可以有多匹马。
请问能否将棋盘上所有的马移动到同一个位置,若可以请输出移动的最小步数。若不可以输出 0。
输入描述
输入m 和 n 两个数,m 和 n 表示一个 m*n 的棋盘。输入棋盘内的数据。
输出描述
能否将棋盘上所有的马移动到同一个位置,若可以请输入移动的最小步数。若不可以输出 0。
示例一
输入
3 2
. .
2 .
. .
输出
0
示例二
输入
3 5
4 7 . 4 8
4 7 4 4 .
7 . . . .
输出
17
解题思路
单匹马的跳跃情况
假设已知某匹马的坐标和最大跳跃步数,则可以用BFS计算出该匹马能够到达地图上某个点的最小步数。比如对于以下初始位于(0, 0)位置最多能跳4步的马
4 . . . .
. . . . .
. . . . .
考虑它跳跃到地图上各个点所花费的步数
跳跃0步
0 . . . .
. . . . .
. . . . .
跳跃1步
0 . . . .
. . 1 . .
. 1 . . .
跳跃2步
0 . 2 . 2
. . 1 2 .
2 1 . . 2
跳跃3步
0 3 2 3 2
3 . 1 2 3
2 1 . 3 2
跳跃4步
0 3 2 3 2
3 4 1 2 3
2 1 4 3 2
因此可以通过BFS过程得到这匹马可以到达的最终状态。其代码如下
from collections import deque
DIERECTIONS = [(1, 2), (1, -2), (-1, 2), (-1, -2), (2, 1), (2, -1), (-2, 1), (-2, -1)]
def bfs4SingleHorse(i, j, m, n, step):
mat = [[-1] * n for _ in range*(m)]
mat[i][j] = 0
q = deque()
q.append((i, j))
level = 0
while q:
level += 1
if level > step:
break
qSize = len(q)
for _ in range(qSize):
cur_i, cur_j = q.popleft()
for di, dj in DIERECTIONS:
nxt_i, nxt_j = cur_i + di, cur_j + dj
if 0 <= nxt_i < m and 0 <= nxt_j < n and mat[nxt_i][nxt_j] == -1:
mat[nxt_i][nxt_j] = level
q.append((nxt_i, nxt_j))
return mat
多匹马的跳跃情况
对于每一匹马,都可以计算出对应的二维矩阵mat。考虑多匹马的情况,将所有马的mat叠加成一个总的二维矩阵ans_mat,对于每一个点(x, y)而言,其逻辑如下
- 若
ans_mat[x][y]已经为-1,说明有其他马无法到达点(x,y) - 若某匹马的
mat[x][y]为-1,说明这匹马无法到达点(x,y),将ans_mat[x][y]改为-1 ans_mat[x][y]和mat[x][y]均不为-1,则将mat[x][y]叠加到ans_mat[x][y]中
考虑2匹马的简单例子,可以从以下例子看出上述逻辑。假设初始矩阵为
3 . . . .
. . 1 . .
. . . . .
那么位置为(0, 0)的马的最终可到达情况矩阵mat为
0 3 2 3 2
3 . 1 2 3
2 1 . 3 2
位置为(1, 2)的马的最终可到达情况矩阵mat为
1 . . . 1
. . 0 . .
1 . . . 1
其中-1用.来表示。两者的叠加结果为
1 . . . 3
. . 1 . .
3 . . . 3
可以看出,所有马跳到同一个位置的最小的步数就为1。
代码
Python
# 欢迎来到「欧弟算法 - 华为OD全攻略」,收录华为OD题库、面试指南、八股文与学员案例!
# 地址:https://www.odalgo.com
# 华为OD机试刷题网站:https://www.algomooc.com
# 添加微信 278166530 获取华为 OD 笔试真题题库和视频
# 题目:【BFS】2024E/2025C-跳马问题
# 分值:200
# 作者:许老师-闭着眼睛学数理化
# 算法:BFS
# 代码看不懂的地方,请直接在群上提问
from collections import deque
from math import inf
# 马走”日“字型的八个方向数组
DIERECTIONS = [(1, 2), (1, -2), (-1, 2), (-1, -2), (2, 1), (2, -1), (-2, 1), (-2, -1)]
# 单匹马进行BFS的函数
# (i, j)为马的起始位置
# step为马能够走的最大步数
def bfs4SingleHorse(i, j, m, n, step):
# 记录这匹马最终的跳跃情况的数组,
# 初始化每一个位置为-1,表示暂且无法到达
# mat也同时可以作为check_list的作用
mat = [[-1] * n for _ in range(m)]
# 马所在的初始位置(i,j)设置到达步数为0
mat[i][j] = 0
q = deque()
q.append((i, j))
# BFS的层数,表示跳到某个位置需要的步数
level = 0
# 进行BFS
while q:
# 层数+1
level += 1
# 如果此时BFS的层数已经超过了这匹马能够跳跃的最大步数step
# 则直接退出循环
if level > step:
break
qSize = len(q)
# 遍历该层的所有点
for _ in range(qSize):
# 弹出队头元素,获得当前点(cur_i, cur_j)
cur_i, cur_j = q.popleft()
# 考虑当前点走“日”字型的八个方向
for di, dj in DIERECTIONS:
# 计算下一个点的到达位置(nxt_i, nxt_j)
nxt_i, nxt_j = cur_i + di, cur_j + dj
# 如果下一个点没有越界,且之前尚未经过(mat起到check_list的作用)
if 0 <= nxt_i < m and 0 <= nxt_j < n and mat[nxt_i][nxt_j] == -1:
# 把mat[nxt_i][nxt_j]修改为到达该点(nxt_i, nxt_j)的最小步数
mat[nxt_i][nxt_j] = level
# 同时该点也需要加入队列中,继续做BFS
q.append((nxt_i, nxt_j))
# 做完BFS,将mat传出函数外
return mat
# 输入地图的长m,宽n
m, n = map(int, input().split())
grid = list()
for _ in range(m):
# 输入地图,由于存在字符'.'
# 所以不需要转化成int整数,储存字符串数组即可
grid.append(list(input().split()))
# 初始化ans_mat,
# ans_mat[x][y]表示【所有马】到达点(x,y)所需的总步数
# 如果无法到达,则最终会被标记为-1
ans_mat = [[0] * n for _ in range(m)]
# 双重循环,遍历原grid中每一个点
for i in range(m):
for j in range(n):
# 如果这个点是数字,则可以计算这匹马最终跳跃状态对应的mat
# 其中最大跳跃步数为int(grid[i][j])
if grid[i][j] != ".":
mat = bfs4SingleHorse(i, j, m, n, int(grid[i][j]))
# 对于算出来的mat,再次遍历每一个位置,更新ans_mat
for x in range(m):
for y in range(n):
# 如果ans[x][y]已经为-1,说明有其他马无法到达点(x,y)
# 如果mat[x][y]为-1,说明这匹马无法到达点(x,y)
# 无论是上述那种情况,都应该把ans_mat[x][y]改为-1
if mat[x][y] == -1 or ans_mat[x][y] == -1:
ans_mat[x][y] = -1
# 否则,将mat[x][y]的值叠加在ans_mat[x][y]中
else:
ans_mat[x][y] += mat[x][y]
# 最终需要输出的最终答案
ans = inf
# 遍历ans_mat中的每一个点,
# 计算出ans_mat中不为-1的最小值
for i in range(m):
for j in range(n):
if ans_mat[i][j] != -1 and ans > ans_mat[i][j]:
ans = ans_mat[i][j]
print(0 if ans == inf else ans)
Java
import java.util.*;
class Main {
static class Pair {
int first;
int second;
Pair(int first, int second) {
this.first = first;
this.second = second;
}
}
static final int[][] DIRECTIONS = {{1, 2}, {1, -2}, {-1, 2}, {-1, -2}, {2, 1}, {2, -1}, {-2, 1}, {-2, -1}};
static int[][] bfs4SingleHorse(int i, int j, int m, int n, int step) {
int[][] mat = new int[m][n];
for (int[] row : mat) {
Arrays.fill(row, -1);
}
mat[i][j] = 0;
Queue<Pair> q = new LinkedList<>();
q.add(new Pair(i, j));
int level = 0;
while (!q.isEmpty()) {
level++;
if (level > step) {
break;
}
int qSize = q.size();
for (int k = 0; k < qSize; k++) {
Pair cur = q.poll();
for (int[] dir : DIRECTIONS) {
int ni = cur.first + dir[0];
int nj = cur.second + dir[1];
if (0 <= ni && ni < m && 0 <= nj && nj < n && mat[ni][nj] == -1) {
mat[ni][nj] = level;
q.add(new Pair(ni, nj));
}
}
}
}
return mat;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int m = scanner.nextInt();
int n = scanner.nextInt();
scanner.nextLine(); // consume newline
String[][] grid = new String[m][n];
for (int i = 0; i < m; i++) {
String line = scanner.nextLine();
String[] tokens = line.split(" ");
for (int j = 0; j < n; j++) {
grid[i][j] = tokens[j];
}
}
int[][] ansMat = new int[m][n];
for (int[] row : ansMat) {
Arrays.fill(row, 0);
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (!grid[i][j].equals(".")) {
int[][] mat = bfs4SingleHorse(i, j, m, n, Integer.parseInt(grid[i][j]));
for (int x = 0; x < m; x++) {
for (int y = 0; y < n; y++) {
if (mat[x][y] == -1 || ansMat[x][y] == -1) {
ansMat[x][y] = -1;
} else {
ansMat[x][y] += mat[x][y];
}
}
}
}
}
}
int ans = Integer.MAX_VALUE;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (ansMat[i][j] != -1 && ans > ansMat[i][j]) {
ans = ansMat[i][j];
}
}
}
System.out.println((ans == Integer.MAX_VALUE) ? 0 : ans);
}
}
C++
#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;
const vector<pair<int, int>> DIRECTIONS = {{1, 2}, {1, -2}, {-1, 2}, {-1, -2}, {2, 1}, {2, -1}, {-2, 1}, {-2, -1}};
vector<vector<int>> bfs4SingleHorse(int i, int j, int m, int n, int step) {
vector<vector<int>> mat(m, vector<int>(n, -1));
mat[i][j] = 0;
queue<pair<int, int>> q;
q.push({i, j});
int level = 0;
while (!q.empty()) {
level++;
if (level > step) {
break;
}
int qSize = q.size();
for (int k = 0; k < qSize; k++) {
pair<int, int> cur = q.front();
q.pop();
for (auto &dir : DIRECTIONS) {
int ni = cur.first + dir.first;
int nj = cur.second + dir.second;
if (0 <= ni && ni < m && 0 <= nj && nj < n && mat[ni][nj] == -1) {
mat[ni][nj] = level;
q.push({ni, nj});
}
}
}
}
return mat;
}
int main() {
int m, n;
cin >> m >> n;
cin.ignore();
vector<vector<string>> grid(m, vector<string>(n));
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
cin >> grid[i][j];
}
}
vector<vector<int>> ansMat(m, vector<int>(n, 0));
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] != ".") {
auto mat = bfs4SingleHorse(i, j, m, n, stoi(grid[i][j]));
for (int x = 0; x < m; x++) {
for (int y = 0; y < n; y++) {
if (mat[x][y] == -1 || ansMat[x][y] == -1) {
ansMat[x][y] = -1;
} else {
ansMat[x][y] += mat[x][y];
}
}
}
}
}
}
int ans = INT_MAX;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (ansMat[i][j] != -1 && ans > ansMat[i][j]) {
ans = ansMat[i][j];
}
}
}
cout << ((ans == INT_MAX) ? 0 : ans) << endl;
return 0;
}
C
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
// 马走“日”字型的八个方向数组
int DIRECTIONS[8][2] = {
{1, 2}, {1, -2}, {-1, 2}, {-1, -2},
{2, 1}, {2, -1}, {-2, 1}, {-2, -1}
};
// 定义队列的结构
typedef struct {
int x, y;
} Point;
typedef struct {
Point *data;
int front, rear;
int capacity;
} Queue;
// 初始化队列
Queue* createQueue(int capacity) {
Queue* q = (Queue*)malloc(sizeof(Queue));
q->data = (Point*)malloc(sizeof(Point) * capacity);
q->front = 0;
q->rear = 0;
q->capacity = capacity;
return q;
}
// 入队
void enqueue(Queue* q, int x, int y) {
q->data[q->rear++] = (Point){x, y};
}
// 出队
Point dequeue(Queue* q) {
return q->data[q->front++];
}
// 判断队列是否为空
int isEmpty(Queue* q) {
return q->front == q->rear;
}
// 单匹马进行BFS的函数
void bfs4SingleHorse(int startX, int startY, int m, int n, int step, int **mat) {
Queue* q = createQueue(m * n);
mat[startX][startY] = 0;
enqueue(q, startX, startY);
int level = 0;
// 进行BFS
while (!isEmpty(q)) {
level++;
if (level > step) break;
int qSize = q->rear - q->front;
for (int i = 0; i < qSize; i++) {
Point cur = dequeue(q);
for (int d = 0; d < 8; d++) {
int nxtX = cur.x + DIRECTIONS[d][0];
int nxtY = cur.y + DIRECTIONS[d][1];
if (nxtX >= 0 && nxtX < m && nxtY >= 0 && nxtY < n && mat[nxtX][nxtY] == -1) {
mat[nxtX][nxtY] = level;
enqueue(q, nxtX, nxtY);
}
}
}
}
free(q->data);
free(q);
}
int main() {
int m, n;
scanf("%d %d", &m, &n);
char grid[m][n][10];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
scanf("%s", grid[i][j]);
}
}
// 初始化ans_mat
int **ans_mat = (int **)malloc(m * sizeof(int *));
for (int i = 0; i < m; i++) {
ans_mat[i] = (int *)malloc(n * sizeof(int));
for (int j = 0; j < n; j++) {
ans_mat[i][j] = 0;
}
}
// 遍历grid中的每个点
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j][0] != '.') {
int step = atoi(grid[i][j]);
int **mat = (int **)malloc(m * sizeof(int *));
for (int x = 0; x < m; x++) {
mat[x] = (int *)malloc(n * sizeof(int));
for (int y = 0; y < n; y++) {
mat[x][y] = -1;
}
}
bfs4SingleHorse(i, j, m, n, step, mat);
for (int x = 0; x < m; x++) {
for (int y = 0; y < n; y++) {
if (mat[x][y] == -1 || ans_mat[x][y] == -1) {
ans_mat[x][y] = -1;
} else {
ans_mat[x][y] += mat[x][y];
}
}
}
for (int x = 0; x < m; x++) {
free(mat[x]);
}
free(mat);
}
}
}
// 找到ans_mat中不为-1的最小值
int ans = INT_MAX;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (ans_mat[i][j] != -1 && ans > ans_mat[i][j]) {
ans = ans_mat[i][j];
}
}
}
printf("%d\n", ans == INT_MAX ? 0 : ans);
for (int i = 0; i < m; i++) {
free(ans_mat[i]);
}
free(ans_mat);
return 0;
}
Node JavaScript
const readline = require("readline");
const DIRECTIONS = [
[1, 2], [1, -2], [-1, 2], [-1, -2],
[2, 1], [2, -1], [-2, 1], [-2, -1]
];
// 单匹马进行BFS的函数
function bfs4SingleHorse(startX, startY, m, n, maxStep) {
// 初始化记录跳跃情况的矩阵
const mat = Array.from({ length: m }, () => Array(n).fill(-1));
mat[startX][startY] = 0;
const queue = [[startX, startY]];
let level = 0;
// 进行BFS
while (queue.length > 0) {
level++;
if (level > maxStep) break;
const qSize = queue.length;
for (let i = 0; i < qSize; i++) {
const [curX, curY] = queue.shift();
for (const [dx, dy] of DIRECTIONS) {
const nxtX = curX + dx;
const nxtY = curY + dy;
if (nxtX >= 0 && nxtX < m && nxtY >= 0 && nxtY < n && mat[nxtX][nxtY] === -1) {
mat[nxtX][nxtY] = level;
queue.push([nxtX, nxtY]);
}
}
}
}
return mat;
}
// 主函数
function main(input) {
const [mn, ...gridInput] = input.split("\n");
const [m, n] = mn.split(" ").map(Number);
const grid = gridInput.map(row => row.split(" "));
const ansMat = Array.from({ length: m }, () => Array(n).fill(0));
// 遍历grid中每个点
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (grid[i][j] !== ".") {
const maxStep = parseInt(grid[i][j], 10);
const mat = bfs4SingleHorse(i, j, m, n, maxStep);
for (let x = 0; x < m; x++) {
for (let y = 0; y < n; y++) {
if (mat[x][y] === -1 || ansMat[x][y] === -1) {
ansMat[x][y] = -1;
} else {
ansMat[x][y] += mat[x][y];
}
}
}
}
}
}
// 找到ansMat中不为-1的最小值
let ans = Infinity;
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (ansMat[i][j] !== -1 && ans > ansMat[i][j]) {
ans = ansMat[i][j];
}
}
}
console.log(ans === Infinity ? 0 : ans);
}
// 输入处理
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout
});
let input = [];
rl.on("line", (line) => input.push(line));
rl.on("close", () => main(input.join("\n")));
Go
package main
import (
"bufio"
"fmt"
"math"
"os"
"strconv"
"strings"
)
// 马走“日”字型的八个方向数组
var DIRECTIONS = [8][2]int{
{1, 2}, {1, -2}, {-1, 2}, {-1, -2},
{2, 1}, {2, -1}, {-2, 1}, {-2, -1},
}
// 单匹马进行BFS的函数
func bfs4SingleHorse(startX, startY, m, n, maxStep int) [][]int {
mat := make([][]int, m)
for i := range mat {
mat[i] = make([]int, n)
for j := range mat[i] {
mat[i][j] = -1
}
}
mat[startX][startY] = 0
queue := [][2]int{{startX, startY}}
level := 0
for len(queue) > 0 {
level++
if level > maxStep {
break
}
qSize := len(queue)
for i := 0; i < qSize; i++ {
curX, curY := queue[0][0], queue[0][1]
queue = queue[1:]
for _, dir := range DIRECTIONS {
nxtX := curX + dir[0]
nxtY := curY + dir[1]
if nxtX >= 0 && nxtX < m && nxtY >= 0 && nxtY < n && mat[nxtX][nxtY] == -1 {
mat[nxtX][nxtY] = level
queue = append(queue, [2]int{nxtX, nxtY})
}
}
}
}
return mat
}
func main() {
// 输入处理
reader := bufio.NewReader(os.Stdin)
firstLine, _ := reader.ReadString('\n')
mn := strings.Fields(firstLine)
m, _ := strconv.Atoi(mn[0])
n, _ := strconv.Atoi(mn[1])
grid := make([][]string, m)
for i := 0; i < m; i++ {
line, _ := reader.ReadString('\n')
grid[i] = strings.Fields(line)
}
// 初始化ansMat
ansMat := make([][]int, m)
for i := range ansMat {
ansMat[i] = make([]int, n)
}
// 遍历grid中每个点
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
if grid[i][j] != "." {
maxStep, _ := strconv.Atoi(grid[i][j])
mat := bfs4SingleHorse(i, j, m, n, maxStep)
for x := 0; x < m; x++ {
for y := 0; y < n; y++ {
if mat[x][y] == -1 || ansMat[x][y] == -1 {
ansMat[x][y] = -1
} else {
ansMat[x][y] += mat[x][y]
}
}
}
}
}
}
// 找到ansMat中不为-1的最小值
ans := math.MaxInt
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
if ansMat[i][j] != -1 && ans > ansMat[i][j] {
ans = ansMat[i][j]
}
}
}
if ans == math.MaxInt {
fmt.Println(0)
} else {
fmt.Println(ans)
}
}
时空复杂度
时间复杂度:O((NM)^2)。
空间复杂度:O(NM)。
华为OD算法/大厂面试高频题算法练习冲刺训练
-
华子OD算法/大厂面试高频题算法冲刺训练目前开始常态化报名!目前已服务1000+同学成功上岸!
-
课程讲师为全网200w+粉丝编程博主@吴师兄学算法 以及小红书头部编程博主@闭着眼睛学数理化
-
90+天陪伴式学习,100+直播课时,300+动画图解视频,500+LeetCode经典题,500+华为OD真题/大厂真题,还有简历修改、模拟面试、陪伴小群、资深HR对接将为你解锁
-
可上全网独家的欧弟OJ系统练习华子OD、大厂真题
-
可查看链接OD真题汇总(持续更新)
-
绿色聊天软件戳
od1441或了解更多
更多推荐
所有评论(0)