华为OD机试真题 - 跳马 (D卷,200分)

题目描述

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

给定 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)，的格点上，但是不可以超出棋盘范围。

目录

题目描述

输入描述

输出描述

用例

题目解析

Java算法源码

JS算法源码

Python算法源码

C算法源码

华为机试有三道题目，第一道和第二道属于简单或中等题，分值为100分，第三道为中等或困难题，分值为200分。总分为400分，150分钟，机试是在牛客考试，练习的时候也可以在牛客网练习，提前熟悉操作

https://ac.nowcoder.com/acm/contest/5652/K

点击上方链接进入牛客练习界面，可以自定义题目，自定义输入、输出等等，华为OD真实机试环境，非其他第三方平台模拟。

输入描述

第一行输入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_VAL