迷宫_逆向

深度优先算法介绍

深度优先搜索算法（Depth-First-Search），是搜索算法的一种。是沿着树的深度遍历树的节点，尽可能深的搜索树的分支。当节点v的所有边都己被探寻过，搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访问为止。属于盲目搜索。

深度优先算法在迷宫中的使用

二维的迷宫：

  • 使用递归的方法，用栈的思想放入和取出路径，用数组的方式存放迷宫图
  • 使用for循环遍历四个方向，在每个节点选择走的方向，如果按这个方向向下走一步能够满足条件（不是墙并且没有到达过），就可以将这一步的目标地址进行标记（已经走过），并且将走的方向放入路径之中
  • 当死路的时候就会向上返回。如果四个方向都遍历，没有一个方向能够满足条件，那么就会返回上一轮，并且将这步错误的方向在路径之中去除，并且将这个地址再次标记为未可达
  • 递归的结束条件。已经到达了目标地址的坐标，就可以返回这个路径了

二维迷宫题算法实现

C语言版本

map：迷宫地图，数组需要在声明的时候进行初始化

stages：上下左右的表示方法

n,m：一共有多少排多少列

stx,sty：迷宫起始的位置，需要对应数组的下标

endx,endy：迷宫终点的位置，需要对应数组相应的下标

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
#include<stdio.h>

char tmap[32][32]={"00000","01100","00100","00110","00000"};
int sign[50][50]={0};
// 右左下上
int next[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
char stages[] = "dasw";
//这个迷宫有几排几列，用于判断有没有超出边界
int n=5,m=5;
// 标记起始位置
int stx=1,sty=1;
// 标记终点位置
int endx=3,endy=3;
// road 路径
char road[1000];
//已经走了多少步了
int steps=0;

void addSteps(char stage){
    road[steps] = stage;
    steps++;
}
void subSteps(){
    steps--;
    road[steps] = NULL;
}
//深度优先算法 提供的参数是走迷宫的起始位置
void dfs(int x,int y){
    int tx,ty;
    if(x == endx&&y == endy){
        //到达了最后的地方
        printf("走的路径是：%s",(char*)road);
        return;
    }

    for(int i=0;i<4;i++){
            //tx 和 ty标记到达地址
            tx = x+next[i][0];
            ty = y+next[i][1];
        // 当沿着这个方向的下一步不是墙 不是已经走过的地方 并且到达的这个地址在范围之内
        if(tx>=0&&tx<n&&ty>=0&&ty<m&&tmap[ty][tx]!='0'&&sign[ty][tx]==0){
            sign[ty][tx]=1;
            //将之前长度的字符串放入到其中 并且再添加一个字符（表示这一步的方向）
            addSteps(stages[i]);
            dfs(tx,ty);
            sign[ty][tx]=0;
            //除去最后一步
            subSteps();

        }

    }
    //当四个方向都不满足的时候跳出循环
    return;
}

int main(int argc, char** argv){
    dfs(stx,sty);
     return 0;
}

运行结果：dssd

python版本

使用脚本的时候根据题目的不同需要进行修改的脚本之中的参数有

map：map使用数字类型的数字表示，还是用char类型的数组表示，map的声明以及每一步的是否正确的判断条件都是不一样的

stx和sty：迷宫的起点，数组的起点是从0开始标识的

endx和endy：迷宫的终点，注意数组的下标

signdirect：题目之中这四个方向所代表的字符都是不一样的，需要根据题目的要求具体的表示

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
# map是迷宫
map = [[0,0,0,0,0],[0,1,1,0,0],[0,0,1,0,0],[0,0,1,1,0],[0,0,0,0,0]]
# 标记该路径是否走过 5*5的数组的表示方法
sign = [[0]*5 for _ in range(5)]
# 起始的位置
stx = 1
sty = 1

# 标记下一步的地址
endx = 0
endy = 0
# 每次走的方向 路径
flag = ""
# 标记走的四个方向
direct = [[1,0],[-1,0],[0,1],[0,-1]]
# 这四个方向的表示方法
signdirect='dasw'


# 深度遍历方法的实现
def dfs(x,y):
  global flag   #注意在函数里面要当全局变量使用的变量一定要在函数之中进行声明！！！！！！
  endx = 0
  endy = 0
  # 到达终点
  if x==finalx and y==finaly:
    print(flag)
    return
  # 未到达终点之前遍历四个方向
  for i in range(len(direct)):
    endx = x+direct[i][0]
    endy = y+direct[i][1]
    if endy>=0 and endy<len(map) and endx>=0 and endx<len(map[0]) and map[endy][endx] == 1 and sign[endy][endx] !=1:
      sign[endy][endx] = 1
      flag=flag+signdirect[i]
      dfs(endx,endy)
      sign[endy][endx] = 0
      flag = flag[:-1]

if __name__ == '__main__':
    dfs(stx,sty)
运行结果： dssd

如果是用字符串的形式声明迷宫时，map的表示方式，及脚本之中需要改变的地方

1
2
3
map = ["00000","01100","00100","00110","00000"]
# 每一步判断条件的 map[endy][endx] == '1' 要修改成满足要求的对应字符而不是数字了
if endy>=0 and endy<len(map) and endx>=0 and endx<len(map[0]) and map[endy][endx] == '1' and sign[endy][endx] !=1:

三维迷宫题的算法实现

python版本

这里需要输入的参数和二维的脚本差不多，只是要多一个z轴上的坐标

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
import sys
map = [[ "aaaaa","aaaaa","aaaae","aaaae","aaeee"],["aaaaa","aaaaa","aaaae","aaaaa","aaaaa"],["aeeaa","aeeaa","eeeae","eaaae","eaaae"],["aaaaa","aaaaa","aaaaa","aaaaa","eaaee"],[ "aaeea","aaaaa","aeeea","eeaea","eaaea"]]

sign = [[[0]*5 for _ in range(5)] for _ in range(5)]
# 标记起始位置
stx = 2
sty = 4
stz = 0
# 标识终点位置
finalx = 2
finaly = 2
finalz = 2
# 标记下一步的地址
endx = 0
endy = 0
endz = 0
# 每次走的方向 路径
flag = ""
# 标记走的四个方向
direct = [[1,0,0],[-1,0,0],[0,1,0],[0,-1,0],[0,0,1],[0,0,-1]]
signdirect='daswxy'
# 深度遍历方法的实现
def dfs(x,y,z):
  global flag   #注意在函数里面要当全局变量使用的变量一定要在函数之中进行声明！！！！！！
  endx = 0
  endy = 0
  endz = 0
  # 到达终点
  if x==finalx and y==finaly and z==finalz:
    print(flag)
    return
  # 未到达终点之前遍历6个
  for i in range(len(direct)):
    endx = x+direct[i][0]
    endy = y+direct[i][1]
    endz = z+direct[i][2]
    if endy>=0 and endy<len(map[0]) and endx>=0 and endx<len(map[0][0]) and endz>=0 and endz<len(map) and map[endz][endy][endx] == 'e' and sign[endz][endy][endx] !=1:
      sign[endz][endy][endx] = 1
      flag=flag+signdirect[i]
      dfs(endx,endy,endz)
      sign[endz][endy][endx] = 0
      flag = flag[:-1]

if __name__ == '__main__':
    dfs(stx,sty,stz)
# 这里返回的结果有多个，选取其中最短的那个即为正确答案   ddwwxxssxaxwwaasasyywwdd
ddwwxxssxaxwwaasasyywwdd
ddwwxxssxaxwwaasasyywwdwds
ddwwxxssxaxwwaasasyywwdwwdss
ddwwxxssxaxwwwasasasyywwdd
ddwwxxssxaxwwwasasasyywwdwds
ddwwxxssxaxwwwasasasyywwdwwdss

有时候迷宫的走法不止一个，就取走的路程最小的那个就可以了