俄罗斯套娃设计文档.doc

“俄罗斯套娃奖品”设计文档题目要求伊万洛夫在比武大会上力克群雄,成为新一届“草原雄鹰”,为部落赢得了莫大荣誉。首领决定要重重奖赏,他对伊万洛夫说:“孩子,你是知道的,面前的这片草原,南北向和东西向的道路纵横交错。现在,路口放着纯金打造的俄罗斯娃娃,重量大小不等,重的都能装下轻的。你可以沿着道路飞奔,拾取路口的娃娃,要求是任何时刻必须是一个套娃,装好后就不能再拆开了。注意不要走重复路。”请你为伊万洛夫规划路线,使得他能够有最大的收获。Input: ;每个测试用例开始是一对整数<R,C>,R表示东西向道路数,C表示南北向道路总数;接下来R行,每行包括C个正整数(或0)W[r,c],分别表示第r条东西向道路与第c条南北向道路交叉处路口放置的俄罗斯娃娃的重量(或表示没有放置娃娃)。Output: 输出能有最大收获的路径规划。平台下VisualC#的控制台应用程序实现,实现算法为动态规划算法。应用程序名称:RussiaDoll主要包括三个模块:1、描述路口坐标的结构体:structPoint{ //路口坐标publicintx;publicinty;}2、描述路口信息的结构体:structNode{publicintvalue;//路口所放俄罗斯套娃的重量publicintmaxValue;//从原点出发到达此路口所能获取到俄罗斯//套娃的最大重量publicPointnextMaxPoint;//从原点出发到达此路口能够有最大的收获的路径中与此路口相邻的//路口坐标}3、求解伊万洛夫能够有最大收获的路线的类:classProgram其类图如下:属性说明:(1)privateintrow;//东西方向道路数(2)privateintcol;//南北方向道路数(3)privateNode[,]data;//描述草原各个路口信息的二维数组(4)privateintlastMaxValue;//能够获取俄罗斯套娃的最大重量(5)privateStringPath="";//能够获取最大收获的路径方法说明:(1)privateboolRead_File(StringfilePath);说明:读取路径为filePath的文件,并对类的相关属性赋值流程图:(2)privatevoidWrite_File(StringfileP