跳马 - 华为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 操作，记录其可抵达的位置马的数量和到达每个位置的最小步数。最后，找到一个位置，其可抵达的马的数量等于总马的数量，且总步数最小，输出最小步数。

以下是解题思路的主要步骤：

1. 遍历棋盘，找到所有马的位置，对每个马进行 BFS 操作。
2. 在 BFS 过程中，记录每个位置被多少匹马抵达，以及每个位置的总步数。
3. 遍历所有位置，找到一个位置，其可抵达的马的数量等于总马的数量，且总步数最小。

这样可以得到最小的总步数，或者如果不存在满足条件的位置，则输出 -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],