首页 > 试题广场 >

逃脱神凛幻域

[编程题]逃脱神凛幻域
  • 热度指数：2588 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解

受到小人的设计，主人公暮小云落入一个名为神凛幻域的奇特地方。对于迷失在这里的人而言这个空间没有绝对的方向，想要脱离这个地方就必须向前走出n步。由于在这个空间内没有方向的概念，无论何时向任何方向迈出一步都是等效的（哪怕你是原地转圈，只要走出N步即可脱离幻境）。不过，由于空间壁垒的原因，不同时刻向不同方向走所耗费的体力不同。现在已知不同时刻向某个方向跨出一步所需耗费的体力，请你告诉暮小云怎么走最省体力，以及需要耗费的最小体力。


输入描述:
有多个输入样例，输入的第一行是样例个数T(1≤T≤50)。每个样例的第一行是一个整数n(1≤n≤100000)。紧接着是四行，依次表示东南西北四个方向的体力耗费情况，每行n个数字，分别表示第n步向该方向走需要花费的体力值xi(0≤xi≤1000000)。某一步的多个方向体力值均为最小值时按照东南西北的顺序取优先方向。


输出描述:
第一行输出需要的最小体力值，第二行输出行走方案分别用符号ESWN表示东南西北。
示例1

输入

1
15
54 66 60 24 100 24 2 67 74 80 55 61 1 51 78
6 52 18 100 95 10 14 15 55 1 8 70 33 2 63
44 24 28 43 52 8 18 58 16 93 67 80 16 33 20
79 2 47 53 88 88 25 59 89 45 89 45 3 72 52

输出

220
SNSEWWESWSSNESW
算法知识视频讲解
开通博客
头像 bandiaoz
发表于 2024-12-26 14:24:25
解题思路 这是一道贪心算法题目，主要思路如下： 问题分析： 每一步都可以选择东南西北四个方向 每个方向都有对应的体力消耗 需要走出 步 目标是最小化总体力消耗 贪心策略： 对于每一步，选择四个方向中体力消耗最小的方向 当多个方向体力值相同时，按东南西北顺序优先选择 记录每一步的选择方 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 hitzyq1
发表于 2021-07-19 16:15:21
import java.util.Scanner; public class Main{ public static int minPhysicalPower = 0; public static String stepScheme = ""; public stat 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 丨阿伟丨
发表于 2025-09-18 16:29:32
题目链接 逃脱神凛幻域 题目描述 需要向前走出 步才能逃脱幻域。由于空间内没有方向的概念，每一步向任何方向走都是等效的。 已知在第 步（）向东、南、西、北四个方向走所分别耗费的体力值。请找出一条总耗费体力最小的路径。 要求： 输出最小的总耗费体力。 输出对应的行走方案字符串（用 'E', 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

动态规划 搜索
上传者：小小
难度：
25条回答 5185浏览

热门推荐

通过挑战的用户

查看代码

相关试题

逃脱神凛幻域

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号