华为机试题-士兵的任务 2

2024-03-15 00:36
文章标签 华为 任务 试题 士兵

本文主要是介绍华为机试题-士兵的任务 2,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目

士兵在迷宫中执行任务,迷宫中危机重重,他需要在在最短的时间内到达指定的位置。你可以告诉土兵他最少需要多长时间吗?
输入一个 n m 的迷宫中,迷宫中 0 为路,1 为墙,2 为起点,3 为终点,4 为陷阱,6 为炸弹。士兵只能向上下左右四个方向移动,如果路径上为墙,不能移动。已知每走一步需要花费 1 个单位的时间,走到陷阱上需要花费 3 个单位的时间,走到炸弹上将会激活炸弹将炸弹上下左右的墙炸为路。
注意点:
1、炸弹只能教毁墙,不会炸掉陷阱
2、炸弹、陷阱只能发挥一次作用
3、迷宫为最大为 25
25
4、用例保证士兵一定有方法能到达终点
解答要求
时间限制: C/C++6000ms,其他语言:12000ms 内存限制:C/C++ 256MB,其他语
言:512MB
输入
第一行:n 和 m
第二行开始:n* m 的矩阵
样例 1
输入:
4 4
1 1 1 1
1 6 2 1
1 1 0 1
1 3 1 1
输出:3
解释:士兵在位置 2,向左移动到炸弹上,会将炸弹周围的墙炸掉,向下走两步即
可到达终点
样例 2
输入:
8 4
1 6 2 1
1 1 0 1
1 1 0 1
1 1 0 1
1 1 0 1
1 1 0 1
1 1 0 1
1 1 3 1
输出:7
解释:士兵在位置 2,向下移动 7 步即可到达终点

参考代码

典型的BFS

import java.util.*;public class soldierMission {static final int[][] DIRECTIONS = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; // 上、下、左、右static final int ROAD = 0, WALL = 1, START = 2, END = 3, TRAP = 4, BOMB = 6;public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();int m = scanner.nextInt();int[][] maze = new int[n][m];for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {maze[i][j] = scanner.nextInt();}}scanner.close();System.out.println(minTimeToReachDestination(maze));}private static int minTimeToReachDestination(int[][] maze) {int n = maze.length;int m = maze[0].length;Queue<State> queue = new LinkedList<>();boolean[][] visited = new boolean[n][m];int startX = -1, startY = -1;// 寻找起点位置for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (maze[i][j] == START) {startX = i;startY = j;break;}}if (startX != -1) break;}// 起点入队queue.offer(new State(startX, startY, 0));visited[startX][startY] = true;while (!queue.isEmpty()) {State current = queue.poll();if (maze[current.x][current.y] == END) {return current.time;}for (int[] direction : DIRECTIONS) {int newX = current.x + direction[0];int newY = current.y + direction[1];if (newX >= 0 && newX < n && newY >= 0 && newY < m && !visited[newX][newY]) {int newTime = current.time + 1;if (maze[newX][newY] == TRAP) {newTime += 2; // 陷阱需要额外花费2个单位时间}// 如果是炸弹,处理炸弹效果if (maze[newX][newY] == BOMB) {maze[newX][newY] = ROAD; // 炸弹被使用,变为路for (int[] d : DIRECTIONS) {int bombX = newX + d[0];int bombY = newY + d[1];if (bombX >= 0 && bombX < n && bombY >= 0 && bombY < m && maze[bombX][bombY] == WALL) {maze[bombX][bombY] = ROAD; // 炸掉周围的墙}}}visited[newX][newY] = true;queue.offer(new State(newX, newY, newTime));}}}// 如果程序运行到这里,说明迷宫构建有误或逻辑错误throw new IllegalStateException("No path found from start to end.");}// 状态类,保存当前位置和到达当前位置所花费的时间static class State {int x, y, time;State(int x, int y, int time) {this.x = x;this.y = y;this.time = time;}}
}

这篇关于华为机试题-士兵的任务 2的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/810245

相关文章

Spring Boot 集成 Quartz并使用Cron 表达式实现定时任务

《SpringBoot集成Quartz并使用Cron表达式实现定时任务》本篇文章介绍了如何在SpringBoot中集成Quartz进行定时任务调度,并通过Cron表达式控制任务... 目录前言1. 添加 Quartz 依赖2. 创建 Quartz 任务3. 配置 Quartz 任务调度4. 启动 Sprin

Linux之计划任务和调度命令at/cron详解

《Linux之计划任务和调度命令at/cron详解》:本文主要介绍Linux之计划任务和调度命令at/cron的使用,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录linux计划任务和调度命令at/cron一、计划任务二、命令{at}介绍三、命令语法及功能 :at

售价599元起! 华为路由器X1/Pro发布 配置与区别一览

《售价599元起!华为路由器X1/Pro发布配置与区别一览》华为路由器X1/Pro发布,有朋友留言问华为路由X1和X1Pro怎么选择,关于这个问题,本期图文将对这二款路由器做了期参数对比,大家看... 华为路由 X1 系列已经正式发布并开启预售,将在 4 月 25 日 10:08 正式开售,两款产品分别为华

SpringQuartz定时任务核心组件JobDetail与Trigger配置

《SpringQuartz定时任务核心组件JobDetail与Trigger配置》Spring框架与Quartz调度器的集成提供了强大而灵活的定时任务解决方案,本文主要介绍了SpringQuartz定... 目录引言一、Spring Quartz基础架构1.1 核心组件概述1.2 Spring集成优势二、J

Redis实现延迟任务的三种方法详解

《Redis实现延迟任务的三种方法详解》延迟任务(DelayedTask)是指在未来的某个时间点,执行相应的任务,本文为大家整理了三种常见的实现方法,感兴趣的小伙伴可以参考一下... 目录1.前言2.Redis如何实现延迟任务3.代码实现3.1. 过期键通知事件实现3.2. 使用ZSet实现延迟任务3.3

Linux中的计划任务(crontab)使用方式

《Linux中的计划任务(crontab)使用方式》:本文主要介绍Linux中的计划任务(crontab)使用方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、前言1、linux的起源与发展2、什么是计划任务(crontab)二、crontab基础1、cro

Spring定时任务只执行一次的原因分析与解决方案

《Spring定时任务只执行一次的原因分析与解决方案》在使用Spring的@Scheduled定时任务时,你是否遇到过任务只执行一次,后续不再触发的情况?这种情况可能由多种原因导致,如未启用调度、线程... 目录1. 问题背景2. Spring定时任务的基本用法3. 为什么定时任务只执行一次?3.1 未启用

如何使用Python实现一个简单的window任务管理器

《如何使用Python实现一个简单的window任务管理器》这篇文章主要为大家详细介绍了如何使用Python实现一个简单的window任务管理器,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起... 任务管理器效果图完整代码import tkinter as tkfrom tkinter i

Spring Boot 集成 Quartz 使用Cron 表达式实现定时任务

《SpringBoot集成Quartz使用Cron表达式实现定时任务》本文介绍了如何在SpringBoot项目中集成Quartz并使用Cron表达式进行任务调度,通过添加Quartz依赖、创... 目录前言1. 添加 Quartz 依赖2. 创建 Quartz 任务3. 配置 Quartz 任务调度4. 启

Java使用多线程处理未知任务数的方案介绍

《Java使用多线程处理未知任务数的方案介绍》这篇文章主要为大家详细介绍了Java如何使用多线程实现处理未知任务数,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 知道任务个数,你可以定义好线程数规则,生成线程数去跑代码说明:1.虚拟线程池:使用 Executors.newVir