html5网站检测,建网站开发国外客户,餐厅网页设计素材,企业门户网站作用华为OD机试 2024D卷题库疯狂收录中#xff0c;刷题点这里 专栏导读
本专栏收录于《华为OD机试#xff08;JAVA#xff09;真题#xff08;D卷C卷A卷B卷#xff09;》。
刷的越多#xff0c;抽中的概率越大#xff0c;每一题都有详细的答题思路、详细的代码注释、样例测… 华为OD机试 2024D卷题库疯狂收录中刷题点这里 专栏导读
本专栏收录于《华为OD机试JAVA真题D卷C卷A卷B卷》。
刷的越多抽中的概率越大每一题都有详细的答题思路、详细的代码注释、样例测试发现新题目随时更新全天CSDN在线答疑。
一、题目描述
马是象棋(包括中国象棋只和国际象棋中的棋子走法是每步直一格再斜一格即先横着或直着走一格然后再斜着走一个对角线可进可退可越过河界俗称马走 “日“ 字。
给项m行n列的棋盘(网格图)棋盘上只有象棋中的棋子“马”并目每个棋子有等级之分等级为K的马可以跳1~k步(走的方式与象棋中“马”的规则一样不可以超出棋盘位置)问是否能将所有马跳到同一位置如果存在输出最少需要的总步数(每匹马的步数相加) 不存在则输出-1。
注意
允许不同的马在跳的过程中跳到同一位置坐标为(x,y)的马跳一次可以跳到到坐标为(x1,y2),(x1,y-2),(x2,y1),(x2,y-1). (x-1,y2),(x-1,y-2),(x-2,y1),(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. …
2、输出
0
3、说明
四、解题思路
棋盘的遍历和马的跳跃规则 我们需要模拟马在棋盘上的跳跃确定所有马是否能到达同一个位置。每个等级为 k 的马可以跳 1 到 k 步但依然遵循“日”字跳跃规则。 广度优先搜索BFS 对于每个马的位置使用广度优先搜索计算从该位置到所有其他位置的最小步数。记录每个马从其起点位置到达所有其他位置的步数。 最小步数计算 对于每个可能的目标位置计算所有马到达该位置的总步数。找到最小的总步数如果存在这样的总步数则输出否则输出 -1。
五、Java算法源码
public class Test01 {private static final int[][] DIRECTIONS {{1, 2}, {1, -2}, {2, 1}, {2, -1},{-1, 2}, {-1, -2}, {-2, 1}, {-2, -1}};public static void main(String[] args) {Scanner scanner new Scanner(System.in);// 读取棋盘的行数和列数int m scanner.nextInt();int n scanner.nextInt();scanner.nextLine(); // 读取换行符char[][] board new char[m][n];Listint[] horses new ArrayList();// 读取棋盘数据for (int i 0; i m; i) {String line scanner.nextLine();for (int j 0; j n; j) {board[i][j] line.charAt(j);if (board[i][j] ! .) {horses.add(new int[]{i, j, board[i][j] - 0}); // 记录马的位置和等级}}}// 关闭Scannerscanner.close();// 计算最小总步数int result findMinimumTotalSteps(board, horses, m, n);System.out.println(result);}// 计算最小总步数private static int findMinimumTotalSteps(char[][] board, Listint[] horses, int m, int n) {int minSteps Integer.MAX_VALUE;boolean isReachable false;// 遍历每个格点作为目标位置for (int i 0; i m; i) {for (int j 0; j n; j) {int totalSteps 0;boolean allReachable true;for (int[] horse : horses) {int steps bfs(board, horse, i, j, m, n);if (steps -1) {allReachable false;break;}totalSteps steps;}if (allReachable) {isReachable true;minSteps Math.min(minSteps, totalSteps);}}}return isReachable ? minSteps : -1;}// 广度优先搜索计算从起点到目标位置的最小步数private static int bfs(char[][] board, int[] horse, int targetX, int targetY, int m, int n) {int startX horse[0];int startY horse[1];int level horse[2];if (startX targetX startY targetY) {return 0;}boolean[][] visited new boolean[m][n];Queueint[] queue new LinkedList();queue.add(new int[]{startX, startY, 0}); // (x, y, steps)visited[startX][startY] true;while (!queue.isEmpty()) {int[] current queue.poll();int x current[0];int y current[1];int steps current[2];for (int k 1; k level; k) {for (int[] direction : DIRECTIONS) {int newX x k * direction[0];int newY y k * direction[1];if (newX targetX newY targetY) {return steps 1;}if (isValid(newX, newY, m, n) !visited[newX][newY]) {visited[newX][newY] true;queue.add(new int[]{newX, newY, steps 1});}}}}return -1;}// 检查坐标是否在棋盘范围内private static boolean isValid(int x, int y, int m, int n) {return x 0 x m y 0 y n;}
}六、效果展示
1、输入
3 5 47.48 4744. 7…
2、输出
16
3、说明 下一篇华为OD机试 - 简易内存池 - 逻辑分析Java 2024 C卷 200分
本文收录于华为OD机试JAVA真题D卷C卷A卷B卷
刷的越多抽中的概率越大每一题都有详细的答题思路、详细的代码注释、样例测试发现新题目随时更新全天CSDN在线答疑。
