华为OD机试：跳马

题目描述

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

给定 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），代表此格点存在等级为 k 的“马”

输出描述

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

用例

题目解析

1.首先，我们需要找到棋盘上所有马的位置，以及它们的等级。

2.然后，我们可以使用广度优先搜索（BFS）算法来解决这个问题。从每个马的位置开始，我们可以尝试跳1~k步，直到找到一个可以跳到同一位置的路径。

3.在搜索过程中，我们需要记录已经访问过的位置，以避免重复搜索。

4.如果找到了一个可以跳到同一位置的路径，我们可以计算总步数并返回结果。如果没有找到这样的路径，我们返回-1。

JS算法源码
 
 const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

void (async function () {
   const [m, n] = (await readline()).split(" ").map(Number);

   const reach = new Set();
   const map = [];
   const stepMap = new Array(m).fill(0).map(() => new Array(n).fill(0));
   const offsets = [[1, 2], [1, -2], [2, 1], [2, -1], [-1, 2], [-1, -2], [-2, 1], [-2, -1]];

   for (let i = 0; i < m; i++) {
     map.push(await readline());
     for (let j = 0; j < n; j++) {
       reach.add(i * n + j);  
     }
   }

   function isValid(x, y) {
     return x >= 0 && x < m && y >= 0 && y < n;
   }

   function getNewPos(x, y, offsetX, offsetY) {
     return [x + offsetX, y + offsetY];
   }

   function bfs(sx, sy, k) {
     let queue = [[sx, sy, 0]];
     const vis = new Set();
     vis.add(sx * n + sy);  

     while (queue.length > 0 && k > 0) {
        const newQueue = [];
        for (let [x, y, step] of queue) {
          for (let [offsetX, offsetY] of offsets) {
            const [newX, newY] = getNewPos(x, y, offsetX, offsetY);
            const pos = newX * n + newY;
            if (!isValid(newX, newY) || vis.has(pos)) continue;
            newQueue.push([newX, newY, step + 1]);
            stepMap[newX][newY] += step + 1;
            vis.add(pos);
          }
        }
        queue = newQueue;
        k--;  
     }
   }

   function getResult() {
     for (let i = 0; i < m; i++) {
       for (let j = 0; j < n; j++) {
         if (map[i][j] != ".") {
           const k = parseInt(map[i][j]);
           bfs(i, j, k);
         }
       }
     }

     if (reach.size == 0) return -1;
     let minStep = Infinity;
     for (let pos of reach) {
       const y = pos % n;
       const x = (pos - y) / n;
       minStep = Math.min(minStep, stepMap[x][y]);
     }
     return minStep;
   }

   console.log(getResult());
})();

Java算法源码
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Scanner;

public class Main { 
  static int m; 
  static int n; 
  static char[][] map; 
  static int[][] stepMap; 
  static HashSet<Integer> reach;

  
  static int[][] offsets = {{1, 2}, {1, -2}, {2, 1}, {2, -1}, {-1, 2}, {-1, -2}, {-2, 1}, {-2, -1}};

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);

    m = sc.nextInt();
    n = sc.nextInt();

    map = new char[m][n];
    stepMap = new int[m][n];
    reach = new HashSet<>();

    for (int i = 0; i < m; i++) {
      map[i] = sc.next().toCharArray();

     
      for (int j = 0; j < n; j++) {
        reach.add(i * n + j);
      }
    }

    System.out.println(getResult());
  }

  public static int getResult() {
   
    for (int i = 0; i < m; i++) {
      for (int j = 0; j < n; j++) {
       
        if (map[i][j] != '.') {
        
          int k = map[i][j] - '0';
          
          bfs(i, j, k);
        }
      }
    }

      if (reach.size() == 0) {
      return -1;
    }

     int minStep = Integer.MAX_VALUE;

    for (int pos : reach) {
      int x = pos / n;
      int y = pos % n;
       minStep = Math.min(minStep, stepMap[x][y]);
    }

    return minStep;
  }

   public static void bfs(int sx, int sy, int k) {
     LinkedList<int[]> queue = new LinkedList<>();
     queue.add(new int[] {sx, sy, 0});

      HashSet<Integer> vis = new HashSet<>();
    vis.add(sx * n + sy);  

     while (queue.size() > 0 && k > 0) {
        LinkedList<int[]> newQueue = new LinkedList<>();

       for (int[] tmp : queue) {
          int x = tmp[0];
        int y = tmp[1];
        int step = tmp[2];

        for (int[] offset : offsets) {
           int newX = x + offset[0];
          int newY = y + offset[1];

          int pos = newX * n + newY;

           if (newX < 0 || newX >= m || newY < 0 || newY >= n || vis.contains(pos)) continue;

           newQueue.add(new int[] {newX, newY, step + 1});
            stepMap[newX][newY] += step + 1;
           vis.add(pos);
        }
      }

      queue = newQueue;
      k--;  
    }

      reach.retainAll(vis);
  }
}

Python算法源码
import sys
from collections import deque

# 输入获取
m, n = map(int, input().split())  # 棋盘行数， 棋盘列数
grid = [input() for _ in range(m)]  # 棋盘矩阵
stepGrid = [[0] * n for _ in range(m)]  # 最小步数和矩阵，stepMap[i][j]记录各个马走到棋盘(i,j)位置的最小步数之和

# 记录所有马都可达的公共位置坐标
reach = set()
for i in range(m):
    for j in range(n):
        reach.add(i * n + j)

# 马走日的偏移量
offsets = ((1, 2), (1, -2), (2, 1), (2, -1), (-1, 2), (-1, -2), (-2, 1), (-2, -1))


# 广搜
def bfs(sx, sy, k):
    global reach

    # 广搜队列
    # (sx,sy)为马所在初始位置，马到达初始位置需要0步
    queue = deque([(sx, sy, 0)])

    # 记录该马可以访问(sx,sy)位置
    vis = set()
    vis.add(sx * n + sy)  # 二维坐标一维化

    # k记录该马剩余可走步数
    while len(queue) > 0 and k > 0:
        # newQueue记录该马花费相同步数的可达的位置（即BFS按层遍历的层）
        newQueue = deque()

        # 按层BFS
        for x, y, step in queue:
            for offsetX, offsetY in offsets:
                # 马走日到达的新位置
                newX = x + offsetX
                newY = y + offsetY

                pos = newX * n + newY

                # 如果新位置越界或者已访问过，则不能访问
                if newX < 0 or newX >= m or newY < 0 or newY >= n or (pos in vis):
                    continue

                # 将新位置加入新层
                newQueue.append((newX, newY, step + 1))

                # 该马到达(newX, newY)位置最小步数为step+1, 由于该马首次到达(newX, newY)位置，因此step+1就是最小步数
                stepGrid[newX][newY] += step + 1

                # 记录该马访问过该位置，后续如果该马再次访问该位置，则不是最小步数
                vis.add(pos)

        queue = newQueue
        k -= 1  # 剩余步数减1

    # BFS完后，将公共可达位置reach和当前马可达位置vis取交集，交集部分就是新的公共可达位置
    reach &= vis


# 算法入口
def getResult():
    # 遍历棋盘
    for i in range(m):
        for j in range(n):
            # 如果棋盘(i,j)位置是马
            if grid[i][j] != '.':
                # 马的等级
                k = int(grid[i][j])
                # 对该马进行BFS走日
                bfs(i, j, k)

    # 如果所有马走完，发现没有公共可达位置
    if len(reach) == 0:
        return -1

    # 记录所有马都可达位置的最小步数和
    minStep = sys.maxsize

    for pos in reach:
        x = pos // n
        y = pos % n
        # (x,y)是所有马都可达的位置，stepMap[x][y]记录所有马到达此位置的步数和
        minStep = min(minStep, stepGrid[x][y])

    return minStep


# 算法调用
print(getResult())

C算法源码
#include <stdio.h>
#include <limits.h>
#include <math.h>

#define MAX_SIZE 26

int m, n;

char map[MAX_SIZE][MAX_SIZE];
int stepMap[MAX_SIZE][MAX_SIZE] = {0};

int reach[MAX_SIZE * MAX_SIZE] = {0};
int reach_size = 0;

int offsets[8][2] = {{1,  2},
                     {1,  -2},
                     {2,  1},
                     {2,  -1},
                     {-1, 2},
                     {-1, -2},
                     {-2, 1},
                     {-2, -1}};

void bfs(int sx, int sy, int k) {
    int queue[m * n][3];
    int queue_size = 0;

    queue[queue_size][0] = sx;
    queue[queue_size][1] = sy;
    queue[queue_size][2] = 0;

    queue_size++;

    int vis[MAX_SIZE * MAX_SIZE] = {0};
    vis[sx * n + sy] = 1;

    while (queue_size > 0 && k > 0) {
        int newQueue[m * n][3];
        int newQueue_size = 0;

        for (int i = 0; i < queue_size; i++) {
            int x = queue[i][0];
            int y = queue[i][1];
            int step = queue[i][2];

            for (int j = 0; j < 8; j++) {
                int newX = x + offsets[j][0];
                int newY = y + offsets[j][1];

                int pos = newX * n + newY;

                if (newX < 0 || newX >= m || newY < 0 || newY >= n || vis[pos]) continue;

                newQueue[newQueue_size][0] = newX;
                newQueue[newQueue_size][1] = newY;
                newQueue[newQueue_size][2] = step + 1;

                newQueue_size++;

                stepMap[newX][newY] += step + 1;

                vis[pos] = 1;
            }
        }

        for (int i = 0; i < newQueue_size; i++) {
            queue[i][0] = newQueue[i][0];
            queue[i][1] = newQueue[i][1];
            queue[i][2] = newQueue[i][2];
        }
        queue_size = newQueue_size;

        k--;  
    }

    for (int i = 0; i < m * n; i++) {
        if (reach[i] == 1 && !vis[i]) {
            reach[i] = 0;
            reach_size--;
        }
    }
}

int getResult() {
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (map[i][j] != '.') {
                int k = map[i][j] - '0';
                bfs(i, j, k);
            }
        }
    }

    if (reach_size == 0) {
        return -1;
    }

    int minStep = INT_MAX;

    for (int i = 0; i < m * n; i++) {
        if(reach[i] != 1) continue;
        
        int x = i / n;
        int y = i % n;
         minStep = (int) fmin(minStep, stepMap[x][y]);
    }

    return minStep;
}

int main() {
    scanf("%d %d", &m, &n);

    for (int i = 0; i < m; i++) {
        scanf("%s", map[i]);

        for (int j = 0; j < n; j++) {
            reach[i * n + j] = 1;
        }
    }

    reach_size = m * n;

    printf("%d\n", getResult());

    return 0;
}