Matlab深度优先搜索求解迷宫所有解

qibbxxt

这两天有空看了看数据结构，决定写一个迷宫所有路径的程序(其实前一段时间玩cody,也遇到过这个问题，不过那个时候用的比较啰嗦的方法，有时间我会把别人优秀的算法贴出来)，希望大家一起交流

1. function DFS_Maze(maze)
   
2. % 本函数用深度优先遍历（回溯法）来求解迷宫的所有路径
   
3. % maze:是迷宫矩阵，其中0表示可以去走的路
   
4. %                     1表示障碍
   
5. %                     2表示入口
   
6. %                     3表示出径
   
7. %                     5表示路径
   
8. %             0 2 0 0 1
   
9. %             0 1 1 0 1
   
10. %             0 1 3 0 1
    
11. %             0 1 0 0 1
    
12. % copyright: qbb 2013-3-12
    
13. if nargin == 0
    
14.     maze = [0 2 0 0 1
    
15.         0 1 1 0 1
    
16.         0 1 3 0 1
    
17.         0 1 0 0 1];
    
18. end
    
19. % 定义四个方向
    
20. directions = kron(eye(2),[-1,1]);
    
21. % 路径个数
    
22. sol = 0;
    
23. [I,J] = find(maze == 2);% 找到起点
    
24. search(I,J);
    
25. disp(sol);
    
26. % 该函数判断该点是否可以经过
    
27.     function z = cango(x,y)
    
28.         % 用try来判断边界
    
29.         z = true;
    
30.         try
    
31.             if ismember(maze(x,y),[1,2,5])% 路障或者已经走过
    
32.                 z = false;
    
33.             end
    
34.         catch
    
35.             z = false; % 边界
    
36.         end
    
37.     end
    
38.     function search(x,y)
    
39.         if maze(x,y) == 3 % 找到出口
    
40.             disp(maze);   % 打印路径
    
41.             sol = sol + 1;% 解的个数增加
    
42.             return        % 返回
    
43.         end
    
44.         % 搜索4个方向
    
45.         for i = 1 : 4
    
46.             if cango(x + directions(1,i),y + directions(2,i)) % 如果可以走
    
47.                 if maze(x + directions(1,i),y + directions(2,i)) ~= 3
    
48.                     maze(x + directions(1,i),y + directions(2,i)) = 5;% 记录下来
    
49.                 end
    
50.                 search(x + directions(1,i),y + directions(2,i)); % 继续寻找下一个点
    
51.                 if maze(x + directions(1,i),y + directions(2,i)) ~= 3
    
52.                     maze(x + directions(1,i),y + directions(2,i)) = 0; % 回到该节点，继续寻找下一个方向
    
53.                 end
    
54.             end
    
55.         end
    
56.     end
    
57. end

复制代码

运行结果

1. >> DFS_Maze
   
2.      0     2     5     5     1
   
3.      0     1     1     5     1
   
4.      0     1     3     5     1
   
5.      0     1     5     5     1
   

复制代码

1.      0     2     5     5     1
   
2.      0     1     1     5     1
   
3.      0     1     3     5     1
   
4.      0     1     0     0     1
   

复制代码

1. 2

复制代码