动态规划-迷宫-百度之星-Labyrinth

Labyrinth

 

Problem Description

度度熊是一只喜欢探险的熊,一次偶然落进了一个m*n矩阵的迷宫,该迷宫只能从矩阵左上角第一个方格开始走,只有走到右上角的第一个格子才算走出迷宫,每一次只能走一格,且只能向上向下向右走以前没有走过的格子,每一个格子中都有一些金币(或正或负,有可能遇到强盗拦路抢劫,度度熊身上金币可以为负,需要给强盗写欠条),度度熊刚开始时身上金币数为0,问度度熊走出迷宫时候身上最多有多少金币?

Input

输入的第一行是一个整数T(T < 200),表示共有T组数据。每组数据的第一行输入两个正整数m,n(m<=100,n<=100)。接下来的m行,每行n个整数,分别代表相应格子中能得到金币的数量,每个整数都大于等于-100且小于等于100。

Output

对于每组数据,首先需要输出单独一行”Case #?:”,其中问号处应填入当前的数据组数,组数从1开始计算。每组测试数据输出一行,输出一个整数,代表根据最优的打法,你走到右上角时可以获得的最大金币数目。

Sample Input

2

3 4

1 -1 1 0

2 -2 4 2

3 5 1 -90

2 2

1 1

1 1

Sample Output

Case #1:

18

Case #2:

4

迷宫规模较大,DFS必然超时。注意到行走方向只有上、下、右三个,意味着已走过的路不能再走,更意味着不用回溯。且问题问的是最大值。一切都清晰地指向了DP!

时间复杂度: O(n*n*m)。

 

时间: 2014-05-16

动态规划-迷宫-百度之星-Labyrinth的相关文章

一道百度之星编程大赛题的随笔联想·(2)

百度之星,是全球最大的中文搜索引擎,百度公司面向中国高校学生和编程爱好者所举办的高水平的程序设计大赛.他所考试的题目,全部都是算法的题目. 鄙人虽然是一个.net程序员,在工作之余,喜爱算法. 我觉得这个题目有点意思,故而分享给大家,我想到两种方法,提供大家,希望对大家起了一个开阔思路的作用. 下面介绍解法二了.  解法二,是抓小放大.  由小及大.首先,说一说我分析的思路吧.  第一步,还是判断i是不小于i/2,以此循环了.  第二步,是不是判断此范围的值的累加是不是等于相应某个值. 第三步,

百度之星试题每周一练

百度之星,是全球最大的中文搜索引擎,百度公司面向中国高校学生和编程爱好者所举办的高水平的程序设计大赛.他所考试的题目,全部都是算法的题目. 鄙人虽然是一个.net程序员,在工作之余,喜爱算法. 这个问题非常的巧,故而分享给大家,我想到一种超简单方法,提供大家,希望对大家起了一个开阔思路的作用. 首先,题意是这样的: 八方块移动游戏要求从一个含 8 个数字 (用 1-8 表示) 的方块以及一个空格方块 (用 0 表示) 的 3x3 矩阵的起始状态开始,不断移动该空格方块以使其和相邻的方块互换,直至

一道百度之星编程大赛题的随笔联想·(1)

百度之星,是全球最大的中文搜索引擎,百度公司面向中国高校学生和编程爱好者所举办的高水平的程序设计大赛.他所考试的题目,全部都是算法的题目. 鄙人虽然是一个.net程序员,在工作之余,喜爱算法. 我觉得这个题目有点意思,故而分享给大家,我想到两种方法,提供大家,希望对大家起了一个开阔思路的作用. 首先,看题目是那样的: 请编写程序,根据输入的任何一个正整数,找出符合这种要求的所有连续正整数序列. 输入数据:一个正整数,以命令行参数的形式提供给程序. 输出数据:在标准输出上打印出符合题目描述的全部正

由一道百度之星题目写起 谈谈编程中的分类的思想

百度之星,是全球最大的中文搜索引擎,百度公司面向中国高校学生和编程爱好者所举办的高水平的程序设计大赛.他所考试的题目,全部都是算法的题目. 鄙人虽然是一个非主流的.net程序员,在工作之余,喜爱算法. 我觉得这个题目有点意思,故而分享给大家,我想到两种方法,提供大家,希望对大家起了一个开阔思路的作用. 更重要想谈一谈算法中的分治算法. 首先,题目是那样的: 请编写程序,找出下面"输入数据及格式"中所描述的输入数据文件中最大重叠区间的大小. 对一个正整数n,如果n在数据文件中某行的两个正

动态规划-hdoj-4832-百度之星2014初赛第二场

Chess Problem Description 小度和小良最近又迷上了下棋.棋盘一共有N行M列,我们可以把左上角的格子定为(1,1),右下角的格子定为(N,M).在他们的规则中,"王"在棋盘上的走法遵循十字路线.也就是说,如果"王"当前在(x,y)点,小度在下一步可以移动到(x+1, y), (x-1, y), (x, y+1), (x, y-1), (x+2, y), (x-2, y), (x, y+2), (x, y-2) 这八个点中的任意一个. 小度觉得每

10年百度之星编程赛复赛题目(蜗牛)求答案代码

问题描述 10年百度之星编程赛复赛题目(蜗牛)求答案代码 ?一只蜗牛某天早晨掉进了深为L尺的井中.蜗牛每天白天可以向上爬若干尺,晚上休息时会向下滑若干尺.蜗牛一旦 到达井口或井底,便不再下滑.假设蜗牛每天向上爬的尺数均为不超过10的正整数,而下滑的尺数为不超过5的正整数.蜗牛在第N天白天里(含第N天白天结束时)爬出了井,你的任务是统计有多少种可能的爬升/下滑情况.对于两种爬升/下滑情况,当存在对应的白天上爬或者晚上下滑的尺数不同时,即视为不同的情况.输入格式第一行:井深L.其中L为正整数,且L<

2016&quot;百度之星&quot; - 初赛(Astar Round2B)解题报告

此文章可以使用目录功能哟↑(点击上方[+]) 被自己蠢哭,去年还能进一下复赛,今年复赛都没戏了... 链接→2016"百度之星" - 初赛(Astar Round2B)  Problem 1001 区间的价值 Accept: 0    Submit: 0 Time Limit: 10000/5000 mSec(Java/Others)    Memory Limit : 65536 KB  Problem Description  Input  Output  Sample Input

第五届“Astar百度之星程序设计大赛”正式向全国高校学生启动

本报讯(记者高天赋 实习生沈梦菲)近日,第五届"Astar百度之星程序设计大赛"正式面向全国高校学生启动. "Astar百度之星程序设计大赛"是百度公司从2005年起创办的一项校园赛事,旨在为广大程序设计爱好者搭建一个比试身手.切磋交流的平台,大赛创办至今已经吸引了数万名参与者,众多程序设计高手通过大赛脱颖而出. 据介绍,今年的"Astar百度之星程序设计大赛"面向全国所有高校的在校学生,不分年级.专业,均可报名参加,通过在线资格赛.晋级赛等一系

百度之星总冠军乔明达:编程就像玩游戏有趣

在百度之星的历届冠军选手中,乔明达无疑是一个让人大跌眼镜的存在.2013年,这个来自南京外国语学校的17岁少年将冠军宝座收入囊中,赢得了现场一片不可思议的惊叹.在以往的接触中,乔明达给我们留下的印象是一个面对镜头局促羞涩,私下却总是笑容满面,亲切的如同邻家弟弟的大男孩. 正是这个大男孩,在国内外各项赛事中都取得过令人瞩目的成绩:第5届亚洲与太平洋地区信息学http://www.aliyun.com/zixun/aggregation/34147.html">奥林匹克竞赛国际金牌(2011年