广度优先搜索 找到迷宫中的最短路径

2744557306

clear all
clc
maze=[0,0,0,0,0,0,0,0;
0 W% a5 N; `1 ^      0,1,1,1,1,0,1,0;
& h3 a8 h6 j. o1 i/ y      0,0,0,0,1,0,1,0;
3 @, [2 `  V0 _0 A. m      0,1,0,0,0,0,1,0;
" G" ]6 V2 f- x$ n: S7 y      0,1,0,1,1,0,1,0;
      0,1,0,0,0,0,1,1;
! j7 ]3 s2 }3 h2 h8 o$ \      0,1,0,0,1,0,0,0;
      0,1,1,1,1,1,1,0];%迷宫:0为路,1为墙,-1为遍历过
4 U  e% h' S, t# {! t* y2 [fx(1:4)=[1,-1,0,0];
fy(1:4)=[0,0,-1,1];
sq.pre=zeros(1,100);sq.x=zeros(1,100);sq.y=zeros(1,100);
qh=0;%队头指针
; H5 w" w( e/ n6 ^: zqe=1;%队尾指针
3 _) k* ~$ P9 P# wmaze(1,1)=-1;
  Q( u) s" j0 a+ }1 e4 j%第一个元素入队
sq.pre(1)=0;sq.x(1)=1;sq.y(1)=1;

while qh-qe~=0
qh=qh+1;
bb=0;
; y+ c9 O. W* H  `for k=1:4
i=sq.x(qh)+fx(k);
j=sq.y(qh)+fy(k);
, P  H! k! w; [6 G+ t( I2 Hif check(i,j,maze)==1
qe=qe+1;%入队
) Y- U6 [% b* Xsq.x(qe)=i;sq.y(qe)=j;sq.pre(qe)=qh;
maze(i,j)=-1;
2 N3 T4 ^- B2 H7 P+ b- `, P3 \0 G5 w
" f  Y8 Q! z: J5 ]: }, I. Mif i==8&j==8%如果为图最后一个点
% N- \  \2 e- L) R& {( q; f+ Dwhile qe~=0
sq.x(qe)
6 Q0 C3 L- W) |/ `, g, psq.y(qe)   
qe=sq.pre(qe);
end
9 ]3 U( ^4 q1 p/ a1 s) T+ Gbb=1;
+ J6 O2 `6 F# n6 f, p7 T3 e6 tbreak;
% D% m# o  ^8 z+ q+ ]$ K1 Dend %if
end %if
7 k8 D7 p2 l8 F* E& lend
if bb==1
$ Y+ Z: |6 V# v9 y2 C4 U$ Abreak
end
( ^) u7 Q! @* E  G0 J2 y2 mend%while
* y* u2 v. b- q: f( c
3 d- C0 u3 ^' F; |3 a- j
2 v" s! ^8 V# }1 V: _这段代码实现了一个广度优先搜索（BFS）算法，用于找到迷宫中从起点 (1,1) 到终点 (8,8) 的最短路径。
以下是代码的详细解释：

. c+ f, E; O9 x8 K) S% G6 P1.迷宫定义：
2.maze 是一个8x8的矩阵，其中 0 表示可通行的路径，1 表示墙，-1 表示已经遍历过的路径。
3.方向定义：
4.fx 和 fy 定义了四个方向，即上、下、左、右的偏移量。
5.队列定义：
6.sq.pre, sq.x, sq.y 分别用于存储每个点的前一个点、x坐标和y坐标。
! o$ A  k" l8 U! q- l) n7.qh 和 qe 分别是队列的头和尾的指针。
8.初始设置
+ D6 T( [6 e: B$ z" w9.起点 (1,1) 被标记为 -1（已遍历），并加入队列。
10.广度优先搜索：
% X# H* A3 S; S. |+ a% ~2 `6 [11.使用一个 while 循环来进行搜索，直到队列为空。
12.在每一轮中，取出队头的点 (sq.x(qh), sq.y(qh))，然后尝试向四个方向移动。
. X8 J5 |$ b$ d% [13.对于每个方向，如果新的坐标 (i, j) 是有效的（即在迷宫范围内且没有被遍历过），则将其标记为 -1（已遍历）并加入队列。
14.如果新的坐标是终点 (8,8)，则从队列的尾部开始，回溯找到从终点到起点的路径。
15.回溯路径：
% T" T% _; Q+ L16.如果找到终点，那么从 qe 开始，通过 sq.pre 数组回溯每个点的前一个点，直到回到起点。
这样，当代码执行完成后，sq.x 和 sq.y 的值将表示从起点到终点的最短路径。
3 j: @' l$ h/ o# Z! ]

$ S4 ?3 p$ t+ r2 s