复刻龙王后的你be like（bfs）

出题组 未收录题目
1

背景

《原神》复刻了那维莱特，你好不容易垫够够89抽，歪了个七七。作为0氪的你，现在，急需原石。

题目

冒险家协会的凯瑟琳会提供许多委托任务，这是个获取原石的好时机。这些任务分布在不同的区域且有先后顺序和前置条件的限制。每个委托任务完成后都会获得一定数量的冒险阅历和原石奖励。现在请你找出从给定的起始区域开始，按照规则能够完成的委托任务序列，使得获得的原石奖励总和最大，并输出这个委托任务序列以及最大原石奖励总和和走的最少步数。

输入

  • 第一行输入两个整数 m 和 n，分别表示区域地图的行数和列数。
  • 接下来的 m 行，每行包含 n 个字符，表示区域地图信息。其中 '#' 表示不可通行的区域（如山脉、河流等），'.' 表示可通行的区域，大写字母 A - Z 表示可接取委托任务的区域。
  • 然后输入一个整数 t，表示委托任务的数量。
  • 接下来的 t 行，每行输入委托任务的相关信息：任务名称、任务所在区域、完成该任务所需前置区域列表（若没有则为空列表 []）、完成该任务可获得的原石奖励数量。
  • 最后一行输入起始区域（行＋列，1开始）。

输出

  • 输出能够获得最大原石奖励的委托任务序列以及对应的最大原石奖励总和和步数，中间用换行符分隔。如果存在多个最优解，输出其中任意一个即可。

示例输入

5 5
.....
.#A..
..#B.
.C...
.....
4
Task1 A [] 20
Task2 B [A] 30 
Task3 C [B] 25
Task4 D [C] 15
2 3

示例输出

Task1 -> Task2 -> Task3
75
5
1 个赞
2

你也在编题目！

3

（样例由AI生成）

样例输入 1

3 3
...
.A.
...
3
Task1 A [] 10
Task2 B [] 15
Task3 C [] 8
1 2

样例输出 1

Task1
10
1

样例输入 2

4 4
....
.#A.
.B#.
....
3
Task1 A [] 5
Task2 B [A] 8
Task3 C [B] 3
1 2

样例输出 2

Task1 -> Task2
13
3

样例输入 3

5 5
.....
..A..
.#B..
..C..
.....
4
Task1 A [] 12
Task2 B [A] 9
Task3 C [B] 10
Task4 D [C] 7
2 2

样例输出 3

Task1 -> Task2 -> Task3
31
5

样例输入 4

6 6
......
..A...
.#B...
...C..
..D...
......
5
Task1 A [] 8
Task2 B [A] 6
Task3 C [B] 9
Task4 D [C] 5
Task5 E [D] 4
2 2

样例输出 4

Task1 -> Task2 -> Task3 -> Task4
28
7

样例输入 5

4 4
....
.A..
..B.
....
3
Task1 A [] 15
Task2 B [A] 12
Task3 C [B] 9
1 2

样例输出 5

Task1 -> Task2
27
3

样例输入 6

5 5
.....
.A#..
..B..
.#C..
.....
4
Task1 A [] 7
Task2 B [A] 6
Task3 C [B] 8
Task4 D [C] 5
1 2

样例输出 6

Task1 -> Task2 -> Task3
21
5

样例输入 7

3 3
...
.A.
.B.
3
Task1 A [] 18
Task2 B [A] 16
Task3 C [B] 12
1 2

样例输出 7

Task1 -> Task2
34
2

样例输入 8

6 6
......
..A...
.#B...
...C..
..D...
......
5
Task1 A [] 5
Task2 B [A] 7
Task3 C [B] 6
Task4 D [C] 8
Task5 E [D] 4
2 2

样例输出 8

Task1 -> Task2 -> Task3 -> Task4
26
7

样例输入 9

4 4
....
.A..
..B.
.C..
4
Task1 A [] 9
Task2 B [A] 8
Task3 C [B] 7
Task4 D [C] 6
1 2

样例输出 9

Task1 -> Task2 -> Task3
24
4

样例输入 10

6 6
.###..
#A..#.
#.B.#.
#..C#.
#D..#.
#E...
6
Task1 A [] 10
Task2 B [A] 15
Task3 C [B] 12
Task4 D [C] 8
Task5 E [D] 9
Task6 F [A,E] 20
3 2

样例输出 10

Task1 -> Task6
30
5

样例输入 11

8 8
........
#.A.#...
#...#.B.
#.C#...#
#...#.D.
#E.#...#
#...#.F.
........
8
Task1 A [] 12
Task2 B [A] 9
Task3 C [A] 10
Task4 D [B,C] 15
Task5 E [D] 8
Task6 F [D] 11
Task7 G [E,F] 18
Task8 H [G] 6
4 2

样例输出 11

Task1 -> Task3 -> Task4 -> Task6 -> Task7
65
11
1 个赞
4

%%%肝

5

我觉得这道题最难的是输入（doge

1 个赞
6

题目看都不想看

7

I am like "bfs".

8

样例好像有错啊王老师

9

根据规则完善标签哦！