思路：BFS

首先我们考虑，如果只有一个马，那肯定是不需要移动的，因此对应的最小步数为0，如果是两个马，我们可以对这两个马分别跑一遍BFS，求这两个马到棋盘上每个点的最小距离（有的点受限于$k$可能到不了），如果有$u$个马，我们可以预处理出这$m$个马到棋盘上的所有距离（不能到达的点距离标记为无穷大），然后我们可以枚举整个棋盘的所有位置，枚举到$(i,j)$位置时，我们可以累加所有马到$(i,j)$点的最短距离，即为$\sum_{v=1}^{u}dist[v][i][j]$，然后更新全局最小值，如果最终的最小值仍然为无穷大，则为无解，输出-1即可。

JavaScript

const readline = require('readline');
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

let n, m, dx, dy, dist, g = [], pos = [];

// 广度优先搜索函数，用于计算从马的当前位置出发到达(i, j)的最短距离
function bfs(x, y, u, k) {
    const queue = [];
    queue.push([x, y]);
    dist[u][x][y] = 0;

    while (queue.length > 0) {
        const [x1, y1] = queue.shift();

        // 遍历八个方向
        for (let i = 0; i < 8; i++) {
            const x2 = x1 + dx[i];
            const y2 = y1 + dy[i];

            // 检查新位置是否在棋盘内，是否满足条件
            if (x2 >= 0 && x2 < n && y2 >= 0 && y2 < m &&
                dist[u][x2][y2] > dist[u][x1][y1] + 1 &&
                dist[u][x1][y1] < k) {
                // 更新最短距离，并将新位置加入队列
                dist[u][x2][y2] = dist[u][x1][y1] + 1;
                queue.push([x2, y2]);
            }
        }
    }
}

rl.on('line', (line) => {
    const lines = line.trim().split(' ');

    if (!n) {
        // 读取第一行输入，初始化变量
        n = parseInt(lines[0]);
        m = parseInt(lines[1]);
        dx = [1, 1, -1, -1, 2, 2, -2, -2];
        dy = [-2, 2, -2, 2, -1, 1, -1, 1];
        dist = {};
    } else {
        // 读取棋盘每一行的输入
        const row = line.split('');
        const i = g.length;
        g.push(row);

        for (let j = 0; j < m; j++) {
            const u = i * m + j;
            // 初始化每个马到所有位置的最短距离
            dist[u] = Array.from({ length: n }, () => Array(m).fill(0x3f3f3f3f));

            if ('1' <= row[j] && row[j] <= '9') {
                // 如果当前位置有马，则进行广度优先搜索
                bfs(i, j, u, parseInt(row[j]));
                pos.push([i, j]);  // 记录马的位置
            }
        }
    }
}).on('close', () => {
    // 计算所有可能的马的位置到每个空白格的最短距离和
    let ans = 0x3f3f3f3f;

    for (let i = 0; i < n; i++) {
        for (let j = 0; j < m; j++) {
            let cnt = 0;

            for (const p of pos) {
                const u = p[0] * m + p[1];

                if (dist[u][i][j] === 0x3f3f3f3f) {
                    cnt = 0x3f3f3f3f;
                    break;
                }

                cnt += dist[u][i][j];
            }

            ans = Math.min(ans, cnt);
        }
    }

    // 输出结果
    if (ans === 0x3f3f3f3f) {
        console.log("-1");
    } else {
        console.log(ans);
    }
});

Java

import java.util.*;

public class Main {
    static final int N = 30;
    static char[][] g = new char[N][N];
    static int n, m;
    static int[] dx = {1, 1, -1, -1, 2, 2, -2, -2};
    static int[] dy = {-2, 2, -2, 2, -1, 1, -1, 1};
    static HashMap<Integer, ArrayList<ArrayList<Integer>>> dist = new HashMap<>();

    // BFS算法，计算从马的当前位置出发到达目标位置(i, j)的最短距离
    static void bfs(int x, int y, int u, int k) {
        Queue<AbstractMap.SimpleEntry<Integer, Integer>> q = new LinkedList<>();
        q.add(new AbstractMap.SimpleEntry<>(x, y));
        dist.get(u).get(x).set(y, 0);

        while (!q.isEmpty()) {
            AbstractMap.SimpleEntry<Integer, Integer> p = q.poll();
            int x1 = p.getKey(), y1 = p.getValue();

            for (int i = 0; i < 8; i++) {
                int x2 = x1 + dx[i], y2 = y1 + dy[i];

                // 判断是否越界，以及是否已经访问过，距离是否超过了k
                if (x2 < 0 || x2 >= n || y2 < 0 || y2 >= m || dist.get(u).get(x2).get(y2) <= dist.get(u).get(x1).get(y1) + 1 || dist.get(u).get(x1).get(y1) >= k) {
                    continue;
                }

                dist.get(u).get(x2).set(y2, dist.get(u).get(x1).get(y1) + 1);
                q.add(new AbstractMap.SimpleEntry<>(x2, y2));
            }
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        ArrayList<AbstractMap.SimpleEntry<Integer, Integer>> pos = new ArrayList<>();
        char[][] g = new char[n][m];

        // 遍历输入地图
        for (int i = 0; i < n; i++) {
            String line = sc.next();
            for (int j = 0; j < m; j++) {
                int u = i * m + j;
                dist.put(u, new ArrayList<>());

                for (int p = 0; p < n; p++) {
                    ArrayList<Integer> row = new ArrayList<>();
                    for (int q = 0; q < m; q++) {
                        row.add(0x3f3f3f3f);
                    }
                    dist.get(u).add(row);
                }

                g[i][j] = line.charAt(j);

                // 如果当前位置是马的起点，则进行BFS计算最短距离，并将起点位置加入pos列表
                if (g[i][j] >= '1' && g[i][j] <= '9') {
                    bfs(i, j, u, g[i][j] - '0');
                    pos.add(new AbstractMap.SimpleEntry<>(i, j));
                }
            }
        }

        int ans = 0x3f3f3f3f;

        // 遍历所有可能的目标位置
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                int cnt = 0;

                // 遍历所有马的起点位置，计算到达目标位置的总距离
                for (AbstractMap.SimpleEntry<Integer, Integer> p : pos) {
                    int u = p.getKey() * m + p.getValue();

                    // 如果有某个马无法到达目标位置，则将cnt设为无穷大
                    if (dist.get(u).get(i).get(j) == 0x3f3f3f3f) {
                        cnt = 0x3f3f3f3f;
                        break;
                    }

                    cnt += dist.get(u).get(i).get(j);
                }

                // 更新最终答案为所有目标位置中的最小值
                ans = Math.min(ans, cnt);
            }
        }

        // 输出最终答案，如果无法到达任何目标位置，则输出-1
        if (ans == 0x3f3f3f3f) System.out.println("-1");
        else System.out.print(ans + System.lineSeparator());
    }
}

Python

from collections import deque

N = 30
g = [[''] * N for _ in range(N)]
n, m = 0, 0
dx = [1, 1, -1, -1, 2, 2, -2, -2]
dy = [-2, 2, -2, 2, -1, 1, -1, 1]
dist = {}

def bfs(x, y, u, k):
    q = deque([(x, y)])
    dist[u][x][y] = 0
    while q:
        x1, y1 = q.popleft()
        for i in range(8):
            x2, y2 = x1 + dx[i], y1 + dy[i]
            if 0 <= x2 < n and 0 <= y2 < m and dist[u][x2][y2] > dist[u][x1][y1] + 1 and dist[u][x1][y1] < k:
                dist[u][x2][y2] = dist[u][x1][y1] + 1
                q.append((x2, y2))

def main():
    global n, m
    global g
    global dist
    n, m = map(int, input().split())
    pos = []
    
    # 读取地图信息
    for i in range(n):
        line = input()
        for j in range(m):
            u = i * m + j
            dist[u] = [[0x3f3f3f3f] * m for _ in range(n)]
            g[i][j] = line[j]
            if '1' <= g[i][j] <= '9':
                # 对每个马的起点进行BFS计算最短距离，并将起点位置加入pos列表
                bfs(i, j, u, int(g[i][j]))
                pos.append((i, j))

    ans = 0x3f3f3f3f
    for i in range(n):
        for j in range(m):
            cnt = 0
            for p in pos:
                u = p[0] * m + p[1]
                # 如果有某个马无法到达目标位置，则将cnt设为无穷大
                if dist[u][i][j] == 0x3f3f3f3f:
                    cnt = 0x3f3f3f3f
                    break
                cnt += dist[u][i][j]
            # 更新最终答案为所有目标位置中的最小值
            ans = min(ans, cnt)

    # 输出最终答案，如果无法到达任何目标位置，则输出-1
    if ans == 0x3f3f3f3f:
        print("-1")
    else:
        print(ans)

if __name__ == "__main__":
    main()

C++

#include<bits/stdc++.h>
using namespace std;
const int N = 30;
char g[N][N];               // 存储地图
int n, m;                   // 地图的行数和列数
int dx[8] = {1, 1, -1, -1, 2, 2, -2, -2};   // 马的移动方向（x轴）
int dy[8] = {-2, 2, -2, 2, -1, 1, -1, 1};   // 马的移动方向（y轴）
unordered_map<int, vector<vector<int>>> dist;   // 标记从每一个马的当前位置出发到达(i, j)的最短距离

// BFS算法，计算从马的当前位置出发到达目标位置(i, j)的最短距离
void bfs(int x, int y, int u, int k) {
    queue<pair<int, int>> q;
    q.push({x, y});
    dist[u][x][y] = 0;

    while (q.size()) {
        auto [x1, y1] = q.front();
        q.pop();

        for (int i = 0; i < 8; i++) {
            int x2 = x1 + dx[i], y2 = y1 + dy[i];

            // 判断是否越界，以及是否已经访问过，距离是否超过了k
            if (x2 < 0 || x2 >= n || y2 < 0 || y2 >= m || dist[u][x2][y2] <= dist[u][x1][y1] + 1 || dist[u][x1][y1] >= k) {
                continue;
            }

            dist[u][x2][y2] = dist[u][x1][y1] + 1;
            q.push({x2, y2});
        }
    }
}

int main() {
    cin >> n >> m;   // 输入地图的行数和列数
    vector<pair<int, int>> pos;   // 存储马的初始位置

    // 遍历输入地图
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            int u = i * m + j;
            dist[u] = vector<vector<int>>(n, vector<int>(m, 0x3f3f3f3f));  // 初始化距离为无穷大
            cin >> g[i][j];

            // 如果当前位置是马的起点，则进行BFS计算最短距离，并将起点位置加入pos列表
            if (g[i][j] >= '1' && g[i][j] <= '9') {
                bfs(i, j, u, g[i][j] - '0');
                pos.push_back({i, j});
            }
        }
    }

    int ans = 0x3f3f3f3f;   // 初始化最终答案为无穷大

    // 遍历所有可能的目标位置
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            int cnt = 0;

            // 遍历所有马的起点位置，计算到达目标位置的总距离
            for (auto &p : pos) {
                int u = p.first * m + p.second;

                // 如果有某个马无法到达目标位置，则将cnt设为无穷大
                if (dist[u][i][j] == 0x3f3f3f3f) {
                    cnt = 0x3f3f3f3f;
                    break;
                }

                cnt += dist[u][i][j];
            }

            // 更新最终答案为所有目标位置中的最小值
            ans = min(ans, cnt);
        }
    }

    // 输出最终答案，如果无法到达任何目标位置，则输出-1
    if (ans == 0x3f3f3f3f) puts("-1");
    else cout << ans << endl;

    return 0;
}

题目描述

马是象棋(包括中国象棋和国际象棋)中的棋子，走法是每步直一格再斜一格，即先横着或直着走一格，然后再斜着走一个对角线，可进可退，可越过河界，俗称马走“日”字。

给定 $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$ 列的网格图棋盘；

接下来输入 $m$ 行 $n$ 列的网格图棋盘，如果第 $i$ 行，第 $j$ 列的元素为“.”代表此格点没有棋子,如果为数字 $k$ ，代表此格点存在等级为 $k$ 的“马”。

• $1\le m,n \le 25$
• $1\le k \le 9$

输出描述

输出最少需要的总步数(每匹马的步数相加)，不存在则输出 $-1$ 。

示例1

输入

3 2
..
2.
..

输出

0

说明：

只有一匹马，不需要跳。

示例2

输入

3 5
47.48
4744.
7....

输出

17