首页 > 试题广场 >

逃脱神凛幻域

[编程题]逃脱神凛幻域

热度指数：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

算法知识视频讲解

Python3

TS9527

贪心。每一步选代价最小的。

class MainActivity:

    def main(self):
        # Read the data
        t = int(input())
        for _ in range(t):
            n = int(input())
            prices = []
            for __ in range(4):
                prices.append(list(map(int, filter(lambda x: len(x) > 0, input().split(' ')))))
            # Initialization
            result = 0
            steps = []
            # Traverse
            for stepIdx in range(n):
                tmpMin = float('+inf')
                tmpMinStep = ''
                for ptr, direction in enumerate(('E', 'S', 'W', 'N')):
                    if prices[ptr][stepIdx] < tmpMin:
                        tmpMin = prices[ptr][stepIdx]
                        tmpMinStep = direction
                result += tmpMin
                steps.append(tmpMinStep)
            print(result)
            print(''.join(steps))


if __name__ == '__main__':
    M = MainActivity()
    M.main()

发表于 2024-09-02 13:58:40 回复(0)