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

2744557306

clear all
$ w4 t+ J+ j3 cclc
maze=[0,0,0,0,0,0,0,0;
      0,1,1,1,1,0,1,0;
      0,0,0,0,1,0,1,0;
      0,1,0,0,0,0,1,0;
      0,1,0,1,1,0,1,0;
3 \8 P) q3 p: `* [. }      0,1,0,0,0,0,1,1;
. K* d- S; p, e0 G8 K' m* [      0,1,0,0,1,0,0,0;
      0,1,1,1,1,1,1,0];%迷宫:0为路,1为墙,-1为遍历过
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);
+ H. C& z8 Y$ x" hqh=0;%队头指针
qe=1;%队尾指针
maze(1,1)=-1;
%第一个元素入队
sq.pre(1)=0;sq.x(1)=1;sq.y(1)=1;

, d# \* j0 ?/ P5 X3 w" mwhile qh-qe~=0
) F8 M& r+ ~$ @7 A7 z' ?: B4 Xqh=qh+1;
bb=0;
; j$ Y' U* v) C9 Vfor k=1:4
i=sq.x(qh)+fx(k);
j=sq.y(qh)+fy(k);
if check(i,j,maze)==1
qe=qe+1;%入队
sq.x(qe)=i;sq.y(qe)=j;sq.pre(qe)=qh;
maze(i,j)=-1;

# L6 K5 n$ l, V# A  P! |" U' r& dif i==8&j==8%如果为图最后一个点
% k0 [, B/ C+ j/ j) _- pwhile qe~=0
sq.x(qe)
sq.y(qe)   
, q) |; V$ m0 w7 \/ qqe=sq.pre(qe);
end
bb=1;
break;
4 z5 Q6 h6 z+ H# U9 ]! n/ T; dend %if
& v! e: h' O+ W2 {6 zend %if
& C2 q7 d" J* h5 R# s9 @end
if bb==1
break
end
end%while
8 W3 k' K" D( }
& j! k& N. }8 d  }4 X: I$ I
- ?2 I* z: V: j4 {* ~7 U这段代码实现了一个广度优先搜索（BFS）算法，用于找到迷宫中从起点 (1,1) 到终点 (8,8) 的最短路径。
8 B: t- U, h! t- x5 c- n以下是代码的详细解释：

  |0 j9 e2 M% d3 Y9 r2 x1.迷宫定义：
) @! Q" b* l1 y- L8 h  R$ G6 h2.maze 是一个8x8的矩阵，其中 0 表示可通行的路径，1 表示墙，-1 表示已经遍历过的路径。
* a5 ], b$ a: `; T) L& M3.方向定义：
! v! n+ V5 W$ |0 G4.fx 和 fy 定义了四个方向，即上、下、左、右的偏移量。
5.队列定义：
6.sq.pre, sq.x, sq.y 分别用于存储每个点的前一个点、x坐标和y坐标。
7.qh 和 qe 分别是队列的头和尾的指针。
4 W* A7 i' A% H* S9 u8.初始设置
9 O* w* a7 l6 }9.起点 (1,1) 被标记为 -1（已遍历），并加入队列。
/ f: _% H6 ]7 Y* v- w1 Y10.广度优先搜索：
" ]1 P' F/ C& E6 c% ]% u11.使用一个 while 循环来进行搜索，直到队列为空。
3 U# v8 r; C) L4 T& W. y12.在每一轮中，取出队头的点 (sq.x(qh), sq.y(qh))，然后尝试向四个方向移动。
3 C' ^. d; h6 e7 F% V7 S+ w/ E13.对于每个方向，如果新的坐标 (i, j) 是有效的（即在迷宫范围内且没有被遍历过），则将其标记为 -1（已遍历）并加入队列。
14.如果新的坐标是终点 (8,8)，则从队列的尾部开始，回溯找到从终点到起点的路径。
15.回溯路径：
) D6 U: J" B1 t% {5 L; y16.如果找到终点，那么从 qe 开始，通过 sq.pre 数组回溯每个点的前一个点，直到回到起点。
( a3 i/ C3 _# j1 o这样，当代码执行完成后，sq.x 和 sq.y 的值将表示从起点到终点的最短路径。
4 V* Z, }( l5 h8 V
) J# {5 R7 W' }+ M4 S