笔试刷题-滴滴2018-06-05

题目描述：

/**
题目描述
小青蛙有一天不小心落入了一个地下迷宫,小青蛙希望用自己仅剩的体力值P跳出这个地下迷宫。
为了让问题简单,
假设这是一个n*m的格子迷宫,迷宫每个位置为0或者1,0代表这个位置有障碍物,
小青蛙达到不了这个位置;1代表小青蛙可以达到的位置。
小青蛙初始在(0,0)位置,
地下迷宫的出口在(0,m-1)(保证这两个位置都是1,并且保证一定有起点到终点可达的路径),
小青蛙在迷宫中水平移动一个单位距离需要消耗1点体力值,
向上爬一个单位距离需要消耗3个单位的体力值,向下移动不消耗体力值,
当小青蛙的体力值等于0的时候还没有到达出口,小青蛙将无法逃离迷宫。
现在需要你帮助小青蛙计算出能否用仅剩的体力值跳出迷宫(即达到(0,m-1)位置)。

输入描述:
输入包括n+1行:
 第一行为三个整数n,m(3 <= m,n <= 10),P(1 <= P <= 100)
 接下来的n行:
 每行m个0或者1,以空格分隔
输出描述:
如果能逃离迷宫,则输出一行体力消耗最小的路径,输出格式见样例所示;
如果不能逃离迷宫,则输出"Can not escape!"。 测试数据保证答案唯一
示例1
输入
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]
*/

思路如下：

通过BFS方式来暴力遍历，用一个State来维护当前位置和能量，同时需要维护一个点可到达的前一个点，以此最后还原路径。

（注意：题目原点在左下角，需要变换一下与具体数组的坐标变换）

代码如下：

#include<stdio.h>
#include<iostream>
#include<queue>
#include<vector>

#define MAX_M 15
#define MAX_N 15

using namespace std;

struct State{
    int x = -1, y = -1, energy = 0;
    State(){}
    State(int x, int y, int energy){
        this->x = x;
        this->y = y;
        this->energy = energy;
    }
    State(const State &s){
        this->x = s.x;
        this->y = s.y;
        this->energy = s.energy;
    }
};

struct Point{
    int x = -1, y = -1;
    Point(){}
    Point(int x, int y){
        this->x = x;
        this->y = y;
    }
    Point(const Point &p){
        this->x = p.x;
        this->y = p.y;
    }
};

//下 右 左 上顺序来BFS
int dx[4] = {1,0,0,-1};
int dy[4] = {0,1,-1,0};
int cost[4] = {0,1,1,3};

//地图
int board[MAX_M][MAX_N];
bool marked[MAX_M][MAX_N];
int pre[MAX_M][MAX_N];//记录成4位数前两位表示横坐标，后两位表示纵坐标

int main(){
    int M, N, E;
    scanf("%d%d%d", &M, &N, &E);
    for(int m=0; m<M; m++){
        for(int n=0; n<N; n++){
            scanf("%d", &board[m][n]);
            pre[m][n] = -1;
        }
    }
    queue<State> que;
    que.push(State(0,0,E));
    marked[0][0] = true;
    while(!que.empty()){
        State current = que.front();
        que.pop();
        if(current.x==0 && current.y==N-1)
            break;
        for(int d=0; d<4; d++){
            int tx = current.x+dx[d];
            int ty = current.y+dy[d];
            int tenergy = current.energy-cost[d];
            if(tx<0 || tx>=M || ty<0 || ty>=N || board[tx][ty]==0 || marked[tx][ty] || tenergy<0)
                continue;
            que.push(State(tx, ty, tenergy));
            marked[tx][ty] = true;
            pre[tx][ty] = current.x*100+current.y;
        }
    }
    if(pre[0][N-1]==-1)
        printf("Can not escape!");
    else{
        vector<Point> paths;
        Point p = Point(0,N-1);
        while(true){
            paths.push_back(p);
            if(p.x==0 && p.y==0)
                break;
            int pre_x = pre[p.x][p.y]/100;
            int pre_y = pre[p.x][p.y]%100;
            p.x = pre_x;
            p.y = pre_y;
        }
        for(int i=paths.size()-1; i>=0; i--){
            p = paths[i];
            printf("[%d,%d]", p.x, p.y);
            if(i)
                printf(",");
        }
    }
    return 0;
}