uva 532 Dungeon Master —— BFS(求最短路)

使用BFS进行正确的求解:

/**
序号:num_7
作者:MrZhang
日期:2016-5-26


题目名称: Dungeon Master(逃离地牢)
题目来源:
uva —— 532 —— Dungeon Master
网址:
英文题目:http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=19489
--------------------------------------
数据样例:
input:

3 4 5
S....
.###.
.##..
###.#
#####
#####
##.##
##...
#####
#####
#.###
####E
1 3 3
S##
#E#
###
0 0 0

output

Escaped in 11 minute(s).
Trapped!
*/

#include iostream
#include cstring
#include queue
#define maxn 31

using namespace std;

typedef struct node{
    int l;
    int r;
    int c;
}Node;

int L,R,C;
char G[maxn][maxn][maxn];
int visited[maxn][maxn][maxn];
int dist[maxn][maxn][maxn];
Node start_node;
queueNode q;

int INF = 27100;//!因为30*30*30,最多有27000的长度。
bool successed;
int _time;//!注意不能命名为"time",原因不明。否则将出现错误:cannot convert 'int' to 'time_t(time_t*) throw () {aka long int(long int*) throw ()}

bool check(int l,int r,int c){
    if(l = 0  l = L-1  r = 0  r = R-1  c = 0  c = C-1){
        if((G[l][r][c] == '.' || G[l][r][c] == 'E')   !visited[l][r][c]){
            return true;
        }
    }

    return false;
}

//!         前后左右上下
int dL[8] = { 0,0,  0,0,  1,-1};
int dR[8] = {-1,1,  0,0,  0, 0};
int dC[8] = { 0,0, -1,1,  0, 0};

void bfs(){
    visited[start_node.l][start_node.r][start_node.c] = 1;
    dist[start_node.l][start_node.r][start_node.c] = 0;
    q.push(start_node);

    while(!q.empty()){
        Node u = q.front();
        q.pop();

        for(int i = 0; i  6;i ++){
            int l2 = u.l + dL[i];
            int r2 = u.r + dR[i];
            int c2 = u.c + dC[i];

             if(check(l2,r2,c2)){
                visited[l2][r2][c2] = 1;
                dist[l2][r2][c2] = dist[u.l][u.r][u.c] + 1;

                if(G[l2][r2][c2] == 'E'){
                    successed = true;
                    _time = dist[l2][r2][c2];
                    return ;
                }

                Node v;
                v.l = l2; v.r = r2; v.c = c2;
                q.push(v);
            }

        }

    }
}

void input(){
    memset(G,'#',sizeof(G));
    memset(visited,0,sizeof(visited));
    memset(dist,0,sizeof(dist));
    while(!q.empty()) q.pop();

    successed = false;
    _time = INF;

    for(int l = 0; l  L; l++){//层数
        for(int r = 0; r  R; r ++){//行数
            for(int c = 0; c  C; c ++){//列数
                cinG[l][r][c];

                if(G[l][r][c] == 'S'){
                    start_node.l = l;
                    start_node.r = r;
                    start_node.c = c;
                }
            }
        }
    }
}

int main(){
    while(cinLRC){
        if(!L!R!C) break;

        input();

        bfs();

        if(successed){
            cout"Escaped in "_time" minute(s)."endl;
        }else{
            cout"Trapped!"endl;
        }
    }

    return 0;
}
/**
总结:
题型:  图的遍历 + 最短路
     ————三维立体图的遍历
原理:BFS(宽度优先搜索)

注意:
   对这一种有某个目的点的问题,在写check()时,终点也是可以通行的点。

补充:针对最短路问题的理解:
求最短路时应使用bfs,以宽度优先进行搜索。
*/


附上使用DFS的错误示例,结果正确,但是超时(Time Limited error)。

/**
错误示例:
原理:DFS。
结果:结果是正确的,但是超时(Time limited error)。
*/
#include iostream
#include cstring

#define maxn 31

using namespace std;
char G[maxn][maxn][maxn];
int visited[maxn][maxn][maxn];
int L,R,C;

int INF = 27100;//!因为30*30*30,最多有27000的长度。

bool successed;
int _time;//!注意不能命名为"time",原因不明。否则将出现错误:cannot convert 'int' to 'time_t(time_t*) throw () {aka long int(long int*) throw ()}
int nowTime;
int s_L,s_R,s_C;

bool check(int l,int r,int c){
    if(l = 0  l = L-1  r = 0  r = R-1  c = 0  c = C-1){
        if((G[l][r][c] == '.' || G[l][r][c] == 'E')   !visited[l][r][c]){
            if(nowTime  _time) return true;
        }
    }

    return false;
}
//!         前后左右上下
int dL[8] = { 0,0,  0,0,  1,-1};
int dR[8] = {-1,1,  0,0,  0, 0};
int dC[8] = { 0,0, -1,1,  0, 0};

void dfs(int l,int r,int c){
    if(G[l][r][c] == 'E'){
        successed = true;
        if(nowTime  _time) _time = nowTime;

        return ;
    }

    for(int i = 0; i  6;i ++){
        int l2 = l + dL[i];
        int r2 = r + dR[i];
        int c2 = c + dC[i];

        if(check(l2,r2,c2)){
            visited[l2][r2][c2] = 1;
            nowTime ++;

            dfs(l2,r2,c2);

            visited[l2][r2][c2] = 0;
            nowTime --;
        }
    }
}

void input(){
    memset(G,'#',sizeof(G));
    memset(visited,0,sizeof(visited));

    successed = false;
    _time = INF;
    nowTime = 0;

    for(int l = 0; l  L; l++){//层数
        for(int r = 0; r  R; r ++){//行数
            for(int c = 0; c  C; c ++){//列数
                cinG[l][r][c];

                if(G[l][r][c] == 'S'){
                    s_L = l;
                    s_R = r;
                    s_C = c;
                }
            }
        }
    }

}

int main(){
    while(cinLRC){
        if(!L!R!C) break;

        input();

        dfs(s_L,s_R,s_C);

        if(successed){
            cout"Escaped in "_time" minute(s)."endl;
        }else{
            cout"Trapped!"endl;
        }
    }

    return 0;
}


最新回复(0)
/jishusOdqlNslm_2FOso2C_2FQ2B_2F6C2_2Fd3mer9vFRCHczenvv4U_3D4795038
8 简首页