首页 > 代码库 > 滴滴出行2017秋招工程岗笔试题-地下迷宫

滴滴出行2017秋招工程岗笔试题-地下迷宫

时间限制: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 // return10 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 energy14 if (n == 0 && m == maze[0].length - 1 && restEnergy < 0) {15 return -oe;16 }17 18 // Reach to exit with non-negative energy19 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秋招工程岗笔试题-地下迷宫