完美未来之星复赛题目之迷宫（5.21） - Tristan's blog
有一个m*n格的迷宫(表示有m行、n列)，其中有可走的也有不可走的，如果用>0表示可以走以及能量的数量，0表示不可以走，每通过1个格子可以收集格子所对应的能量。但是不可以重复走以前走过的格子且只能从左上角到最右下角。怎么样收集的能量才能最多.输入格式
第一行输入1个整数 0 < C < 100 .表示需要处理的迷宫数量。
下面两行分别输入2个整数 3 <= M <= 15, 3 <= N <= 15 分别表示迷宫的行与列
接下来的M行输入 N个数字, 每个数字 0 <= E <= 9
0表示阻挡,无法行走。>0 的数字表示可以通过以及代表的能量数量
注意数字之间没有间隔,行走只能上下左右行走。
输出
可以获得的最大能量数量
输入样例
2
4
4
1100
2110
1110
1111
3
4
1000
0110
1110
输出样例
12
0
分析
数据规模较小，可以用深搜直接解决。每走过一个节点，便将该节点的能量值（权值）置0，当以此节点开始的所有可行路径都走完时，再将该节点值还原，从左上角开始，当节点成功到达数组右下角（迷宫出口）时，则对当前路径获取到的能量总和与当前的最大值进行比较、更新。注意的是输入数据格式，如果用getchar()的话，当输入完数组规模时，此时还有一个回车需要注意过滤。
Read full article from 完美未来之星复赛题目之迷宫（5.21） - Tristan's blog
No comments:
Post a Comment