【來源】網傳的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 }