JiLuo's Blog
0%

迷宫寻宝

发表于 更新于 分类于 ，

题目描述：

　　洪尼玛今天准备去寻宝，在一个n*n （n行, n列）的迷宫中，存在着一个入口、一些墙壁以及一个宝藏。由于迷宫是四连通的，即在迷宫中的一个位置，只能走到与它直接相邻的其他四个位置（上、下、左、右）。现洪尼玛在迷宫的入口处，问他最少需要走几步才能拿到宝藏？若永远无法拿到宝藏，则输出-1。

输入：

　　多组测试数据。

　　每组数据输入第一行为正整数n，表示迷宫大小。

　　接下来n行，每行包括n个字符，其中字符’.’表示该位置为空地，字符’#’表示该位置为墙壁，字符’S’表示该位置为入口，字符’E’表示该位置为宝藏，输入数据中只有这四种字符，并且’S’和’E’仅出现一次。

　　n≤1000

输出：

　　输出拿到宝藏最少需要走的步数，若永远无法拿到宝藏，则输出-1。

Sample Input：

1
2
3
4
5
6
5
S.#..
#.#.#
#.#.#
#...E
#....

Sample Output

1
7

Code 1.0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <stdio.h>
int n,m,sx,sy,ex,ey,step=0;
int visited[1001][1001],min=10000,flag=0; //存放已走过的路径
char map[1001][1001]; //存迷宫
int fx_x[4]={-1,0,1,0}; //(fx_x,fx_y)确定搜索方向
int fx_y[4]={0,1,0,-1};

int dfs(int x,int y,int step){
    int i;
    if (x==ex && y==ey){
        flag=1;
        if(step<min)
            min=step;
        return;
    }

    for (i = 0; i < 4; i++) {
        int tx,ty;
        tx=x+fx_x[i];
        ty=y+fx_y[i];
        if ((map[tx][ty]=='.' || map[tx][ty]=='E') && !visited[tx][ty]) {
            visited[tx][ty]=1;
            dfs(tx,ty,step+1);
            visited[tx][ty]=0;
        }
    }
    return;
}

int main(){
    int i,j;
    //获取行列的值，n为行，m为列
    scanf("%d",&n);
    m=n;
    //存放迷宫地图
    for(i=0;i<n;i++)
        scanf("%s",map[i]);
    //遍历map，获取起点S和终点E的位置
    for (i = 0; i < n; i++) {
        for (j = 0; j < m; j++) {
            if (map[i][j]=='S') {
                sx=i;
                sy=j;
            }
            if (map[i][j]=='E') {
                ex=i;
                ey=j;
            }
        }
    }
    
    visited[sx][sy]=1;
    dfs(sx,sy,step);
    if(flag==1)
        printf("%d",min);
    else
        printf("-1");
}

　　code 1.0 使用了深度优先搜索实现，纯递归回溯，运行效率低，一旦数据量过大，则需要大量的时间进行运算。

Code 2.0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include <iostream>
#include <cstdio>
#include <queue>
using namespace std;

#define N 100
int n,m,s_x,s_y,e_x,e_y;
char map[N][N];
int visited[N][N];

int fx[4]={-1,0,1,0};
int fy[4]={0,1,0,-1};

struct Pointer{
    int x;
    int y;
    int step;
};

queue<Pointer> r;

int main() {
    int flag=0;
    scanf("%d%d",&n,&m);
    for (int i=0; i<n; i++)
            scanf("%s",map[i]);
    
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) {
            if(map[i][j]=='S'){
                s_x=i;
                s_y=j;
                Pointer start;
                start.x=s_x;
                start.y=s_y;
                start.step=0;
                r.push(start);
                visited[s_x][s_y]=1;
            }
            if(map[i][j]=='E'){
                e_x=i;
                e_y=j;
            }
        }
    
    while (!r.empty()) {
        int tx,ty;
        if (r.front().x==e_x && r.front().y==e_y) {
            flag=1;
            printf("%d",r.front().step);
            break;
        }
        for (int i=0; i<4; i++) {
            tx=r.front().x+fx[i];
            ty=r.front().y+fy[i];
            if(!visited[tx][ty] && map[tx][ty]!='#'){
                visited[tx][ty]=1;
                Pointer test;
                test.x=tx;
                test.y=ty;
                test.step=r.front().step+1;
                r.push(test);
            }
        }
        r.pop();
    }
    if (flag==0)
        printf("-1");
    return 0;
}

　　code 1.0 使用了广度优先搜索，效率较高。