『数据结构实训』俄罗斯套娃问题 ——DFS

本文主要是介绍『数据结构实训』俄罗斯套娃问题 ——DFS，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

『问题描述』

---

       伊万洛夫在比武大会上力克群雄，成为新一届“草原雄鹰”，为部落赢得了莫大荣誉。首领决定要重重奖赏，他对伊万洛夫说：“孩子，你是知道的，面前的这片草原，南北向和东西向的道路纵横交错。
现在，路口放着纯金打造的俄罗斯套娃，重量大小不等，重的都能装下轻的。你可以沿着道路飞奔，拾取路口的套娃，要求是任何时刻必须是一个套娃，装好后就不能再拆开了。注意不要走重复路。” 
请你为伊万洛夫规划路线，使得他能够有最大的收获。 
【任务要求】 
        输入包括多组测试用例； 
        每个测试用例开始是一对整数<R, C>，R表示东西向道路数，C表示南北向道路总数；接下来R行，每行包括C个正整数（或0）W[r,c]，分别表示第r条东西向道路与第c条南北向道路交叉处路口放置的俄罗斯娃娃的重量（或0表示没有放置娃娃）。 最终输出能有最大收获的路径规划。 
【样例输入1】：
   2     7 
   1     2   13   6   7  12  11 
   14   3   4     5   8   9   10 
【样例输出1】： 

1 2 3 4 5 6 7 8 9 10 11 12 

【样例输入2】： 
5    5 
1 16  15   14   13 
2 17  24   23   12    
3 18  25   22   11    
4 19  20   21   10 
5  6   7    8    9 
【样例输出2】：

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 
【注释】： 
1)从<0,0>出发; 
2)路线不能重复; 
3)不要求最后回到出发点。

『解题思路』

---

通过观察题目，可以将本题抽象成一个求最大权值的有向图问题，将每个路口看作一个顶点，权值使用w(i)表示。对于相邻两点u和v，当且仅当w(u)<w(v) 或 w(v) == 0时,u和v之间存在弧<u,v>,u为弧尾，v为弧头，其权值为v上权值。 

样例1对应的有向图如下，红色为其最大权值路径。

这篇关于『数据结构实训』俄罗斯套娃问题 ——DFS的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---