华为机试题-士兵的任务 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定时任务只执行一次的原因分析与解决方案

《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

Spring Boot中定时任务Cron表达式的终极指南最佳实践记录

《SpringBoot中定时任务Cron表达式的终极指南最佳实践记录》本文详细介绍了SpringBoot中定时任务的实现方法,特别是Cron表达式的使用技巧和高级用法,从基础语法到复杂场景,从快速启... 目录一、Cron表达式基础1.1 Cron表达式结构1.2 核心语法规则二、Spring Boot中定

定价129元!支持双频 Wi-Fi 5的华为AX1路由器发布

《定价129元!支持双频Wi-Fi5的华为AX1路由器发布》华为上周推出了其最新的入门级Wi-Fi5路由器——华为路由AX1,建议零售价129元,这款路由器配置如何?详细请看下文介... 华为 Wi-Fi 5 路由 AX1 已正式开售,新品支持双频 1200 兆、配有四个千兆网口、提供可视化智能诊断功能,建

Spring Boot 整合 ShedLock 处理定时任务重复执行的问题小结

《SpringBoot整合ShedLock处理定时任务重复执行的问题小结》ShedLock是解决分布式系统中定时任务重复执行问题的Java库,通过在数据库中加锁,确保只有一个节点在指定时间执行... 目录前言什么是 ShedLock?ShedLock 的工作原理:定时任务重复执行China编程的问题使用 Shed

Python Invoke自动化任务库的使用

《PythonInvoke自动化任务库的使用》Invoke是一个强大的Python库,用于编写自动化脚本,本文就来介绍一下PythonInvoke自动化任务库的使用,具有一定的参考价值,感兴趣的可以... 目录什么是 Invoke?如何安装 Invoke?Invoke 基础1. 运行测试2. 构建文档3.

解决Cron定时任务中Pytest脚本无法发送邮件的问题

《解决Cron定时任务中Pytest脚本无法发送邮件的问题》文章探讨解决在Cron定时任务中运行Pytest脚本时邮件发送失败的问题,先优化环境变量,再检查Pytest邮件配置,接着配置文件确保SMT... 目录引言1. 环境变量优化:确保Cron任务可以正确执行解决方案:1.1. 创建一个脚本1.2. 修

Java实现任务管理器性能网络监控数据的方法详解

《Java实现任务管理器性能网络监控数据的方法详解》在现代操作系统中,任务管理器是一个非常重要的工具,用于监控和管理计算机的运行状态,包括CPU使用率、内存占用等,对于开发者和系统管理员来说,了解这些... 目录引言一、背景知识二、准备工作1. Maven依赖2. Gradle依赖三、代码实现四、代码详解五