题目描述

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

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

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

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

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

输入描述

输入m 和 n 两个数，m 和 n 表示一个 m*n 的棋盘。输入棋盘内的数据。

输出描述

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

用例1

输入

3 2
. .
2 .
. .

输出

0

用例二

输入

3 5
4 7 . 4 8
4 7 4 4 .
7 . . . .

输出

17

给定的用例是一个3行5列的棋盘，其中一些位置有数字，代表马的位置和它们可以走的最大步数。我们将逐步模拟广度优先搜索（BFS）的过程来找到所有马都能到达的位置，并计算出最小步数。

棋盘布局：

4 7 . 4 8
4 7 4 4 .
7 . . . .

模拟计算

步骤：

1. 初始化：

   • 马的位置和最大步数分别为：(0,0,4), (0,1,7), (0,3,4), (0,4,8), (1,0,4), (1,1,7), (1,2,4), (1,3,4), (2,0,7)。

2. 对棋盘上的每个位置进行BFS：

   • 我们需要检查棋盘上的每个位置，看看是否所有马都能到达那里。例如，我们检查位置(0,2)。

3. 对每个马进行BFS：

   • 从马(0,0,4)开始，它可以在4步内到达的位置有限。我们将这些位置和步数记录下来，并检查是否包括(0,2)。
   • 接下来，我们对马(0,1,7)执行同样的操作，记录它可以到达的位置和步数。
   • 我们重复这个过程，直到考虑了所有的马。

4. 累加步数：

   • 如果所有马都可以在它们的最大步数内到达位置(0,2)，我们将这些步数累加起来。

5. 更新最小步数：

   • 如果我们发现所有马都能到达位置(0,2)，我们将这个累加的步数与当前的最小步数进行比较，并更新最小步数。
   • 如果有任何一个马不能到达位置(0,2)，我们将忽略这个位置，并继续检查下一个位置。

6. 重复以上步骤：

   • 我们重复以上步骤，对棋盘上的每个位置进行检查。

7. 得出结果：

   • 在检查完所有位置后，我们得到所有马都能到达的位置的最小步数。
   • 如果没有这样的位置，则返回0。

   Java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.HashSet;
import java.util.Set;

public class Main {
    // 定义棋盘的行数和列数
    private static int m, n;
    // 定义棋盘
    private static int[][] board;
    // 定义马的位置和步数的列表
    private static LinkedList<int[]> horses = new LinkedList<>();

    public static void main(String[] args) throws IOException {
        // 使用BufferedReader读取输入
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // 读取第一行输入，获取棋盘的行数和列数
        String[] firstLine = br.readLine().split(" ");
        m = Integer.parseInt(firstLine[0]);
        n = Integer.parseInt(firstLine[1]);
        // 初始化棋盘
        board = new int[m][n];

        // 读取棋盘上每个位置的输入
        for (int i = 0; i < m; i++) {
            String[] line = br.readLine().split(" ");
            for (int j = 0; j