可上 欧弟OJ系统 练习华子OD、大厂真题
绿色聊天软件戳 od1441了解算法冲刺训练(备注【CSDN】否则不通过)

相关推荐阅读

题目练习网址:【BFS】2025C-跳马问题

题目描述与示例

题目描述

输入 mn 两个数,mn 表示一个 m*n 的棋盘。输入棋盘内的数据。棋盘中存在数字和"."两种字符,如果是数字表示该位置是一匹马,如果是"."表示该位置为空的,棋盘内的数字表示为该马能走的最大步数。

例如棋盘内某个位置一个数字为 k,表示该马只能移动 0~k 步的距离。

棋盘内的马移动类似于中国象棋中的马移动,先在水平或者垂直方向上移动一格,然后再将其移动到对角线位置。

棋盘内的马可以移动到同一个位置,同一个位置可以有多匹马。

请问能否将棋盘上所有的马移动到同一个位置,若可以请输出移动的最小步数。若不可以输出 0

输入描述

输入mn 两个数,mn 表示一个 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或了解更多

Logo

Agent 垂直技术社区,欢迎活跃、内容共建。

更多推荐