青蛙走迷宫

【来源】网传的2017滴滴秋招笔试题

【问题描述】
小青蛙有一天不小心落入了一个地下迷宫,小青蛙希望用自己仅剩的体力值P跳出这个地下迷宫。n*m的格子迷宫每个位置为0或者1,1代表可达，0不可达。小青蛙初始在(0,0),地下迷宫的出口在(0,m-1)(保证这两个位置都是1,并且保证一定有起点到终点可达的路径)。小青蛙在迷宫中水平移动一个单位距离需耗1个体力值，向上爬一个单位需耗3个体力值，向下移动不消耗体力值。当小青蛙的体力值等于0的时候还没有到达出口，小青蛙将无法逃离迷宫。
输入描述:
输入包括n+1行:
第一行为三个整数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]

【算法思想】

递归法解，在写程序时重点要理清程序步骤的思路。

【程序】

 1 #include<iostream>
 2 #include<vector>
 3 #include<string.h>
 4 using namespace std;
 5 
 6 int step_x[4] = {-1,1,0,0};
 7 int step_y[4] = { 0, 0, -1, 1 };
 8 int price[4] = {3,0,1,1};
 9 vector<int> xMax;
10 vector<int> yMax;
11 
12 void frog(int maze[11][11],int flag[11][11],int x,int y,int p,int n,int m,vector<int> xPath,vector<int> yPath,int &max_leftp)
13 {
14 
15     if (p < 0){
16         return;
17     }
18 
19     if ( x==0 && y==m-1 ){  //抵达终点后
20         if (max_leftp < p){  //剩余最大体力值存入全局变量Max
21             max_leftp = p;
22             xMax = xPath;
23             yMax = yPath;
24         }
25         return;
26     }
27 
28     for (int i = 0; i < 4;i++){
29         int next_x = x + step_x[i];
30         int next_y = y + step_y[i];
31         if (next_x >= 0 && next_x < n && next_y >= 0 && next_y < m && !flag[next_x][next_y] && maze[next_x][next_y]){
32             flag[next_x][next_y] = 1;
33             xPath.push_back(next_x);
34             yPath.push_back(next_y);
35             frog(maze, flag, next_x, next_y, p-price[i], n, m, xPath, yPath, max_leftp);
36             flag[next_x][next_y] = 0;
37             xPath.pop_back();
38             yPath.pop_back();
39         }
40     }
41 }
42 
43 int main(){
44 
45     int maze[11][11], flag[11][11];
46     memset(maze,0,sizeof(maze)); //初始化为0
47     memset(flag,0,sizeof(flag));
48     vector<int> xPath, yPath;
49     int n, m, p, tmp;
50 
51     cin>>n>>m>>p;
52     for (int i = 0; i < n; i++) {
53         for (int j = 0; j < m; j++) {
54             cin >> tmp;
55             maze[i][j]=tmp;
56         }
57     }
58 
59     //起点
60     flag[0][0] = 1;
61     xPath.push_back(0);
62     yPath.push_back(0);
63 
64     int max_leftp = -100;
65     frog(maze,flag,0,0,p,n,m,xPath,yPath,max_leftp);
66 
67     if (max_leftp == -100){
68         cout << "Can not escape!" << endl;
69     }
70 
71     for (int i = 0; i < xMax.size(); i++){
72         cout << "[" << xMax[i] << "," << yMax[i] << "]";
73         if (i<xMax.size()-1)
74             cout << ",";
75     }
76     cout << endl;
77 
78     return 0;
79 }