- 在线时间
- 472 小时
- 最后登录
- 2025-9-5
- 注册时间
- 2023-7-11
- 听众数
- 4
- 收听数
- 0
- 能力
- 0 分
- 体力
- 7679 点
- 威望
- 0 点
- 阅读权限
- 255
- 积分
- 2884
- 相册
- 0
- 日志
- 0
- 记录
- 0
- 帖子
- 1161
- 主题
- 1176
- 精华
- 0
- 分享
- 0
- 好友
- 1
该用户从未签到
 |
clear all
* ?1 m% h8 D6 c- sclc
n4 j' E/ U: y, l- C1 ]maze=[0,0,0,0,0,0,0,0;1 T5 x& t. R, e% _% O+ y- n/ s5 q
0,1,1,1,1,0,1,0;
+ n9 S( e5 v3 }/ F* ^ 0,0,0,0,1,0,1,0;
3 ~* K8 S) ?3 c4 Q% Y/ N1 c8 B' _ 0,1,0,0,0,0,1,0;
+ i a$ w0 {8 h8 W9 p, d 0,1,0,1,1,0,1,0;% l; k7 g6 h0 g2 U
0,1,0,0,0,0,1,1;
: u! R1 W6 B& r% K" x( g3 {2 j 0,1,0,0,1,0,0,0;
9 ?# w- h* V, r4 w, o' t 0,1,1,1,1,1,1,0];%迷宫:0为路,1为墙,-1为遍历过 f: y4 q0 J0 Q# D
fx(1:4)=[1,-1,0,0];
, |0 D- H+ X# mfy(1:4)=[0,0,-1,1];
9 n+ g3 ~0 l2 n; J0 L4 V, fsq.pre=zeros(1,100);sq.x=zeros(1,100);sq.y=zeros(1,100);+ s0 V# E3 V4 ~- g# E
qh=0;%队头指针( D. m5 G& \, E9 P1 L
qe=1;%队尾指针/ a) z W% p$ j4 X6 Q7 F; X p$ ]
maze(1,1)=-1;
+ f7 \: D1 `: X& b7 A8 H%第一个元素入队
* t2 V: G7 m+ _' y& A& H. m( Tsq.pre(1)=0;sq.x(1)=1;sq.y(1)=1;
/ K: j. y8 U6 j6 K, N# b0 ~5 o6 ?4 o I; m/ T7 ]: w
while qh-qe~=0
+ k% L8 i }0 ^; @7 G x8 }: Vqh=qh+1;* b+ m5 F2 X, e T" c+ N% H6 z- C
bb=0;
2 G$ O' O( H8 I: X% m' |for k=1:4) {! [0 d1 ~1 D
i=sq.x(qh)+fx(k);* u' H) l- Y1 T4 b5 h7 j$ c$ X* X, d
j=sq.y(qh)+fy(k);. a/ f; u4 H# O1 _6 G
if check(i,j,maze)==1
8 G* n# @6 m' [* S. ]qe=qe+1;%入队
& P" N0 n+ n% H1 Gsq.x(qe)=i;sq.y(qe)=j;sq.pre(qe)=qh;3 D. U, D7 D% G& \
maze(i,j)=-1;
2 ]' C/ R7 g) h, a0 u# q) f
I( T( D: ]/ K i0 m# A) Jif i==8&j==8%如果为图最后一个点
9 Z: L7 E' C# p# z0 vwhile qe~=0! s6 H% E8 X' o3 T! n) f6 s
sq.x(qe)
! R7 M5 n) ]. {) |, V/ }5 \) N4 osq.y(qe)
& @- }/ R/ @5 _qe=sq.pre(qe);& r* I- P* |$ a' s8 m# }
end
: Q+ c" E6 o+ ~4 g) rbb=1;
3 k" A% a! L' e, l. }) o Y; Gbreak;. _! R2 w- R2 _( g. t2 Z
end %if/ c' [: _$ E9 D1 A5 G0 v* ?; x) F
end %if) i% N+ x( R# h# u0 n$ {
end
6 [1 @# V9 x( X iif bb==1+ ?! [2 X" ^1 R6 Y' \; j
break" f! ^$ _3 ~3 g* s
end+ P3 B/ _9 Z1 b# O9 ~& k3 I
end%while) R! K0 |) F) i# \; e8 E$ [8 z# t0 S
# b1 [8 ^+ H5 }; A7 }
4 Z4 F' L! g' \这段代码实现了一个广度优先搜索(BFS)算法,用于找到迷宫中从起点 (1,1) 到终点 (8,8) 的最短路径。
2 }/ h1 Y* {5 I" M2 S5 q& z F以下是代码的详细解释:2 R# S5 W( R$ O. Y) n
5 F7 g; \2 m% x% r" A
1.迷宫定义:
+ ]6 t1 O2 I( }" m6 s2.maze 是一个8x8的矩阵,其中 0 表示可通行的路径,1 表示墙,-1 表示已经遍历过的路径。
- Q( k6 L) E G+ \: L1 w9 G3.方向定义:
4 T! a! Q2 B. [; _# ^4.fx 和 fy 定义了四个方向,即上、下、左、右的偏移量。5 H0 y ` e% \4 Z" a6 U8 y
5.队列定义:) Q5 `: L# }, `- ?1 L6 A
6.sq.pre, sq.x, sq.y 分别用于存储每个点的前一个点、x坐标和y坐标。5 e* y& i( w$ ^3 p" d
7.qh 和 qe 分别是队列的头和尾的指针。
3 q' m, N6 ?7 m7 E6 t5 Z8.初始设置* c& W8 N$ E: K
9.起点 (1,1) 被标记为 -1(已遍历),并加入队列。0 Z% ]" x8 A! q3 T5 l5 H
10.广度优先搜索:1 H0 C/ d$ j- c% [9 b% t# C$ _* P
11.使用一个 while 循环来进行搜索,直到队列为空。! `- s$ L# ^5 \5 K$ v/ q
12.在每一轮中,取出队头的点 (sq.x(qh), sq.y(qh)),然后尝试向四个方向移动。: P B6 s+ H) h$ I$ T
13.对于每个方向,如果新的坐标 (i, j) 是有效的(即在迷宫范围内且没有被遍历过),则将其标记为 -1(已遍历)并加入队列。
x( L, g; w# D4 q |! Z14.如果新的坐标是终点 (8,8),则从队列的尾部开始,回溯找到从终点到起点的路径。" W; U6 b4 z6 G# l, H
15.回溯路径:' o, d( _6 S0 G% S+ B- L. p
16.如果找到终点,那么从 qe 开始,通过 sq.pre 数组回溯每个点的前一个点,直到回到起点。
$ c1 w9 D: @. F& s2 Z4 Q& l G这样,当代码执行完成后,sq.x 和 sq.y 的值将表示从起点到终点的最短路径。
/ M5 ]" k# q5 k6 }- X9 A1 N9 O" r/ H
- ^: z. Q( Q& b$ R |
zan
|