关键词：
时间限制：1秒
空间限制：32768k
题目描述
小青蛙有一天不小心落入了一个地下迷宫，小青蛙希望用自己仅剩的体力值P跳出这个地下迷宫。为了让问题简单，假设这是一个n*m的迷宫。迷宫每个位置为0或者1. 0代表这个位置有障碍物，小青蛙到达不了这个位置；1代表小青蛙可以达到的位置。小青蛙初始在(0,0)位置。地下迷宫的出口在(0,m-1)(保证这两个位置都是1，并且保证一定有起点到终点可达的路径)。小青蛙在迷宫中水平移动一个单位距离需要消耗1点体力值。向上爬一个单位距离需要消耗3个体力值，向下移动不消耗体力值。当小青蛙的体力值等于0时候还没有到达出口，小青蛙将无法逃离迷宫。现在需要你帮助小青蛙计算出能否用今生的体力值跳出迷宫（即达到(0,m-1)的位置
输入：
输入 n+1行：
第一行为3个整数n,m(3<=m,n<=10),P(1<=P<=100)
接下来的n行：
每行m个0或者1，以空格分隔
输出：
如果能逃离迷宫，则输出一行体力消耗最小的路径，输出格式见样例所示；如果不能逃离迷宫，则输出“Can not escape!”。
测试数据保证答案唯一
输入例子：
* 4 4 10
* 1 0 0 1
* 1 1 0 1
* 0 1 1 1
* 0 0 1 1
输出例子：
[0,0],[1,0],[1,1],[2,1],[2,2],[2,3],[1,3],[0,3]
这是个典型的Dynamic Programming(动态编程)问题。 现在让我们来分析一下到底应该怎么解答。
首先，出口[0,m-1]和入口[0,0]都已经给定了，也就是说程序入口和出口是固定的。剩下的需要我们找到一条通过路径并好耗费体力最少。也就是说输出的值时最优的。假设最终由[0,0]到[0,m-1]走了k步，那么k步是剩余体力最大的，那么k-1步是不是在到达k前体力剩余最大的呢？答案是肯定的，那么以此类推，我们就可以退出状态转换公式。那么再来看看慢不满足无后效性：从k到k+1步不会对前面已经走过的最优路线产生影响，所以无后效性。那么现在就让我们看一下状态转移方程吧。
===================================华丽的分割线================================================
我们用f[k][i][j]表示剩余体力。这里：k表示第k步，i 行 j 列时候小青蛙的剩余体力。
那么显然：f[0][0][0]=P
f[0][0][m-1]>=0 出口时候体力要大于等于0.
并且每一个f[k][0][m-1]都是要最大化的。
那到底怎么最大化呢？我们知道第 k 步是从 k-1 步来的，有三种走法：从 k-1 向上，向右以及向下，并且每一种走法都对应着不同的体力消耗值。所以我们有：
f[k][i][j] = max( f[k-1][i][j-1]-1 , f[k-1][i+1][j], f[k-1][i-1[j]-3 )
这里有些同学可能要问了，在有些边界情况下是不能向下，向上或者向右的，没关系，我们先写出总的状态方程，然后在每走一步时候对情况进行判定就可以剪去一些不必要的枝叶。具体程序如下：
//输入为二阶迷宫矩阵（n*m）和初始体力值
1 public static void FindPathForFrog(int[][] maze, int P) { 2 Queue<Integer[]> route = new LinkedList<Integer[]>(); 3 if(findPath(maze, P, 0, 0, route, P)<0) 4 System.out.println("Can not escape!"); 5 } 6 7 private static int findPath(int[][] maze, int restEnergy, int n, int m, Queue<Integer[]> route, int oe) { 8 // when out of range or frog cannot get through from this place, then 9 // return 10 if (n < 0 || m < 0 || n > maze.length - 1 || m > maze[0].length - 1 || maze[n][m] == 0 || restEnergy < 0) 11 return -oe; 12 13 // Reach exit with negative energy 14 if (n == 0 && m == maze[0].length - 1 && restEnergy < 0) { 15 return -oe; 16 } 17 18 // Reach to exit with non-negative energy 19 if (n == 0 && m == maze[0].length - 1 && restEnergy >= 0) { 20 route.add(new Integer[] { 0, 0 }); 21 for (Integer[] element : route) { 22 if (element.length != 2) 23 System.err.println("Error ocurred!"); 24 System.out.println("[" + element[0] + "," + element[1] + "]"); 25 } 26 return restEnergy; 27 } 28 // System.out.println("n: " + n + " m: " + m + " rest: " + restEnergy); 29 if (maze[n][m] == 1) 30 route.add(new Integer[] { n, m }); 31 int fromUp = findPath(maze, restEnergy - 3, n + 1, m, route, oe); 32 int fromright = findPath(maze, restEnergy - 1, n, m + 1, route, oe); 33 int fromdown = findPath(maze, restEnergy, n - 1, m, route, oe); 34 35 int mam = Math.max(fromUp, Math.max(fromright, fromdown)); 36 37 if (mam == fromUp) 38 route.add(new Integer[] { n + 1, m }); 39 else if (mam == fromright) 40 route.add(new Integer[] { n, m + 1 }); 41 else if (mam == fromdown) 42 route.add(new Integer[] { n - 1, m }); 43 return mam; 44 }
当然这里有几个地方没有细讲，比如如何输出路径和边界判定，希望阅读的朋友自己动脑经弄懂吧。
滴滴出行秋招编程题
...就这样伤害我自己，手贱。 刷头条看到一篇文章写的滴滴出行2017秋招编程题，后来发现原文在这里http://www.cnblogs.com/SHERO-Vae/p/5882357.html。看了下，挺有意思，于是就想了想，又写了写，最终撸出来了。刚开始一看顿时感觉很... 查看详情
算法是什么我记不住，butidoitmyway.解一道滴滴出行秋招编程题。
...就这样伤害我自己，手贱。 刷头条看到一篇文章写的滴滴出行2017秋招编程题，后来发现原文在这里http://www.cnblogs.com/SHERO-Vae/p/5882357.html。看了下，挺有意思，于是就想了想，又写了写，最终撸出来了。刚开始一看顿时感觉很... 查看详情
2017腾讯秋招笔试题之编码
Description： 假定一种编码的编码范围是a~y的25个字母，从1位到4位的编码，如果我们把该编码按字典序排序，形成一个数组如下：a,aa,aaa,aaaa,aaab,aaac,……,b,ba,baa,baaa,baab,baac……,yyyw,yyyx,yyyy其中a的Index为0，aa的Index为1，aaa的... 查看详情
2017腾讯秋招笔试题之编码
Description： 假定一种编码的编码范围是a~y的25个字母，从1位到4位的编码，如果我们把该编码按字典序排序，形成一个数组如下：a,aa,aaa,aaaa,aaab,aaac,……,b,ba,baa,baaa,baab,baac……,yyyw,yyyx,yyyy其中a的Index为0，aa的Index为1，aaa的... 查看详情
棒谷科技java岗笔试题与初试题
选择题1、银行家算法的作用2、docker镜像结构3、docker的默认网络模式4、spring的动态代理效率比较5、springboot默认的json6、springboot多profile分隔符7、mybatis占位符8、spring异步注解9、spring表达式语言10、高级汇编产生过程11、maven默认... 查看详情
7-24地下迷宫探索（30分）
...侵略者的作战方式。地道网是房连房、街连街、村连村的地下工事，如下图所示。我们在回顾前辈们艰苦卓绝的战争生活的同时，真心钦佩他们的聪明才智。在现在和平发展的年代，对多数人来说，探索地下通道或许只是一种娱... 查看详情
滴滴出行基于rocketmq构建企业级消息队列服务的实践
本文整理自滴滴出行消息队列负责人江海挺在ApacheRocketMQ开发者沙龙北京站的分享。通过本文，您将了解到滴滴出行：在消息队列技术选型方面的思考；为什么选择RocketMQ作为出行业务的消息队列解决方案；如何构建自己的消息... 查看详情
推动系后座安全带，滴滴出行要愚公移山？
...们解决了“打车难”、“打车贵”等难题。不过日前来自滴滴出行一封关于“系好后座安全带”的倡议信却告诉我们：共享经济出行还有更大的社会价值。 滴滴出行在21日发布的倡议信中提出：正确使用安全带，在发生意外... 查看详情
1021:机器人走迷宫（2017年中南大学研究生复试机试题）(代码片段)
1021:机器人走迷宫时间限制:1Sec 内存限制:128MB提交:339 解决:71[提交][状态][讨论版][命题人:外部导入] 题目描述 有一个愚蠢的机器人走进一个w*h的迷宫，迷宫里有空地和陷阱。他想要访问迷宫的每个... 查看详情
数据挖掘2022年2023届秋招kanaries雾角科技算法岗笔试题(代码片段)
Kanaries雾角科技算法岗位笔试笔试时间：2022年10月13号时长：120分钟几乎是刷过的算法题，最后一题是难度题，其他都是中等题目。1、LeetCode2038.如果相邻两个颜色均相同则删除当前颜色（1）题目总共有n个... 查看详情
地下迷宫（bfs输出路径）
题解：开一个pre数组用编号代替当前位置，编号用结构题另存，其实也可以i*m+j来代替，我写的有点麻烦了;代码：#include<iostream>#include<cstdio>#include<cmath>#include<algorithm>#include<cstring>#include<queue>usingnam 查看详情
滴滴出行跨出国门，再战uber胜算有多大？
...中国用户提供跨境租车服务，该服务预计在2016年内登陆滴滴出行APP，届时滴滴用户可以租赁安飞士、巴吉在机场及市区门店的车辆。 众 查看详情
数据挖掘2022年2023届秋招爱玩特智能量化研究员岗笔试题(代码片段)
公司：爱玩特智能岗位：量化研究员时间：2022年10月17号，线下开卷笔试1题目笔试说明1、编程要求语言：Python结果汇总至Excel，表一至表五代码分块汇总至一个python文件、要求注释完整2、数据说明数据库... 查看详情
滴滴出行基于rocketmq构建企业级消息队列服务的实践
小结：1、 https://mp.weixin.qq.com/s/v6NM3UgX-qTI7yO1QPCJrw滴滴出行基于RocketMQ构建企业级消息队列服务的实践原创： 江海挺 阿里巴巴中间件 2018-11-01 查看详情
滴滴出行数据应用平台建设实践
伴随着各种随身设备、物联网和云计算、云存储等技术的发展，数据内容和数据格式多样化，数据颗粒度也愈来愈细，随之出现了分布式存储、分布式计算、流处理等大数据技术，各行业基于多种甚至跨行业的数... 查看详情
(高小德用车)高仿滴滴/快的应用源代码
...大批出行类软件。出行类软件大概有下面几种：打车类：滴滴打车、快的打车 专车类：滴滴专车、一号专车、神州专车 拼车类：嘀嗒拼车、51用车、天天用车高德地图开放平台出行类解决方式-乘客端（iOS）描写叙述使用... 查看详情
滴滴出行大数据数仓实战(代码片段)
文章目录前言1.业务背景2.日志数据集介绍3.构建数据仓库4数据预处理5订单指标分析6Sqoop数据导出7.数据导出操作8Superset数据可视化总结要下的配套资料，已经上传到百度网盘好了大家好,我是ChinaManor,直译过来就是中国码农的... 查看详情
滴滴出行大数据数仓实战(代码片段)
文章目录前言1.业务背景2.日志数据集介绍3.构建数据仓库4数据预处理5订单指标分析6Sqoop数据导出7.数据导出操作8Superset数据可视化总结要下的配套资料，已经上传到百度网盘好了大家好,我是ChinaManor,直译过来就是中国码农的... 查看详情