『数据结构实训』俄罗斯套娃问题 |
您所在的位置:网站首页 › 俄罗斯套娃象征着什么他可以当做什么玩 › 『数据结构实训』俄罗斯套娃问题 |
『问题描述』
伊万洛夫在比武大会上力克群雄,成为新一届“草原雄鹰”,为部落赢得了莫大荣誉。首领决定要重重奖赏,他对伊万洛夫说:“孩子,你是知道的,面前的这片草原,南北向和东西向的道路纵横交错。 现在,路口放着纯金打造的俄罗斯套娃,重量大小不等,重的都能装下轻的。你可以沿着道路飞奔,拾取路口的套娃,要求是任何时刻必须是一个套娃,装好后就不能再拆开了。注意不要走重复路。” 请你为伊万洛夫规划路线,使得他能够有最大的收获。 【任务要求】 输入包括多组测试用例; 每个测试用例开始是一对整数,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)从出发; 2)路线不能重复; 3)不要求最后回到出发点。 『解题思路』通过观察题目,可以将本题抽象成一个求最大权值的有向图问题,将每个路口看作一个顶点,权值使用w(i)表示。对于相邻两点u和v,当且仅当w(u) |
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |