深度优先搜索解决迷宫难题

2744557306

为大家分享一个代码，该代码是使用升读优先搜索解决迷宫难题

当调用[total,maze]=search(1,1,maze,total);时，会从(1, 1)这个位置开始，在给定的迷宫maze上执行深度优先搜索。下面是对代码的逐行解释：
" R& f( L: D% Q+ J8 i+ m
1.function [total,maze]=search(i,j,maze,total);


2.定义了一个函数search，该函数接受当前位置(i, j)、迷宫maze和解的数量total作为输入参数，并返回更新后的total和maze。

# R5 b3 T2 T% J
3.fx(1:4)=[0,1,-1,0];


4.定义了一个包含四个元素的数组fx，表示在行方向上的四个可能的移动。
% D$ J- h8 b5 U3 O5 K: g

5.fy(1:4)=[1,0,0,-1];

8 \) F& t0 X$ }5 ], Z
6.定义了一个包含四个元素的数组fy，表示在列方向上的四个可能的移动。

0 j/ ?! T8 {1 d  p0 p
7.for k=1:4
, _, ?6 {  R# X( \
, p3 X: n% D1 n& `- _
, ]9 W9 F( M- H! M/ b! n% N9 f8.开始一个循环，遍历四个可能的移动方向。
* U7 f9 Q( L* r5 r) C
6 |5 @- d- c5 o8 \
9.newi=i+fx(k);
% n7 y3 m4 W( S! M
# n; K! }; _2 V* N8 E
10.根据当前位置(i, j)和移动方向计算新的行坐标newi。
6 P7 |4 M, l2 B3 ]

$ D( I. X0 ~2 R11.newj=j+fy(k);
& u7 h  C; s$ @$ ~, g* Q8 X( v  u" v6 R

4 V0 t5 V( j1 E; p$ n# d12.根据当前位置(i, j)和移动方向计算新的列坐标newj。


; E1 J# D$ E" |* k# Z: k( W13.if (newi<=8)&(newj<=8)&(newi>=1)&(newj>=1)&maze(newi,newj)==0
( n& g5 o; Z! k) E- ~4 x

# p# \; c0 ]9 U6 o. U14.检查新的位置(newi, newj)是否在迷宫范围内且是可行的（即迷宫中的值为0，表示可以走）。

# Z6 p8 K* `1 ^/ j2 _7 Y
15.maze(newi,newj)=3;
2 O8 P5 ~1 M9 O; ^- ?
; [4 v! Q* z7 f: v1 R+ ]# v$ N( |
16.将迷宫中新的位置标记为3，表示已经走过。

( z. t: a2 y" ?% B' t$ z6 G
17.if newi==8&newj==8
7 F8 g2 S) t# W) O* {

5 H( z) A( Q/ f+ c% r( U  V& y7 G18.如果新的位置是终点(8, 8)，则增加解的数量total，显示当前迷宫maze，并结束递归。
& Z+ r5 B6 V0 u

5 V, \8 }% ]$ M1 V1 y1 `19.total=total+1
- i8 g: E* l7 t3 _# q0 p
  z) {; w, |. z20.增加解的数量。
9 |& a' y; {. V6 B6 u21.maze

3 W4 ]6 `6 y5 t% G0 X22.显示当前的迷宫状态。
5 W% t, R+ T' T2 Q23.else
" E$ X3 G9 l' Z3 `4 {  E0 |% D
* R% A  x* Q; D3 Y3 x. R8 B1 L2 M24.如果新的位置不是终点，执行下面的语句。
25.[total,maze]=search(newi,newj,maze,total);
& }! ], R! p) I  n* C9 ]
; Z# g/ k4 g7 j4 e: @. q26.递归调用search函数，以新的位置(newi, newj)为起点进行搜索。
- _3 _' w. e9 [2 O0 H27.end

+ D  R3 B9 e4 ~& X28.结束if语句。
29.end
5 q1 L, R4 p" }: m
30.结束for循环。
31.maze(i,j)=2;
. L- G+ [) u  |& y
5 Q2 c; c. m7 g' P1 k32.如果所有可能的移动都被尝试过，将当前位置标记为2，表示当前路径是死路。
! E4 w: P  K7 h' ?33.end

1 _3 j: K, p$ d, t$ ?34.结束search函数。
35.clear all
2 ?6 y# \+ s% ?2 u# B  W
! Y. q5 O: `6 C36.清除工作区中的所有变量。
37.clc

38.清空命令窗口。
39.定义了一个8x8的迷宫maze，其中0表示路，1表示墙。
7 i+ D% _: |' s! B# v+ B, f40.total=0;

- A# x/ z( J9 F) f) H41.初始化解的数量。
42.maze(1,1)=3;
6 E: D2 z2 t+ E0 v2 H# s
43.将起始位置标记为3，表示已经走过。
- ]) i, f& w  k) d. F/ b: P6 B44.[total,maze]=search(1,1,maze,total);
# g- o8 ]4 ~2 \1 h
45.调用search函数开始深度优先搜索。

整个过程是通过递归实现深度优先搜索，尝试从起始位置到达终点，并记录所有可能的解。在搜索过程中，迷宫中的可行路径被标记为3，死路被标记为2。搜索结束后，会显示解的数量和每个解对应的迷宫状态。


3 t/ y  `0 y9 ~" `, L8 l

0 j6 p& a4 p% ^  S) ?. l

3 h! G: ?$ b9 T