⑴ 迷宫求解的非递归算法
迷宫求解
任务：可以输入一个任意大小的迷宫数据，用非递归的方法求出一条走出迷宫的路径，并将路径输出；
在资料中请写明：存储结构、基本算法（可以使用程序流程图）、源程序、测试数据和结果、算法的时间复杂度、另外可以提出算法的改进方法；
拜托高手大家些们，我写了个C语言的，但连接编译后才发现25个错误！但我就是找不出来了！麻烦哪位高手给我指点指点！我会追加分的！
#include <stdlib.h>
#include <stdio.h>
#include <conio.h>
#define N 20
int aa[N][N];
int yes=0;
int x[100][2],n=0;
void fun1(int (*aa)[N],int (*a)[N]);
int fun(int (*a)[N],int i,int j);
void begain(int (*t)[N]);
void pr(int (*t)[N],int nn);
void win(int (*t)[N]);
void lose();
void main(void)
{
int t[N][N];
begain(t);
pr(t,0);
fun(t,1,1);
if(yes)
win(t);
else
lose();
getch();
}
void fun1(int (*aa)[N],int (*a)[N])
{
int i,j;
for(i=0;i<N;i++)
for(j=0;j<N;j++)
aa[i][j]=a[i][j];
}
int fun(int (*a)[N],int i,int j)
{
if(i==N-2&&j==N-2)
{
yes=1;
return;
}
a[i][j]=1;
fun1(aa,a);
if(aa[i+1][j+1]==0&&!yes)
{
fun(aa,i+1,j+1);
if(yes)
{x[n][0]=i,x[n++][1]=j;return;}
}
fun1(aa,a);
if(aa[i+1][j]==0&&!yes)
{
fun(aa,i+1,j);
if(yes)
{x[n][0]=i,x[n++][1]=j;return;}
}
fun1(aa,a);
if(aa[i][j+1]==0&&!yes)
{
fun(aa,i,j+1);
if(yes)
{x[n][0]=i,x[n++][1]=j;return;}
}
fun1(aa,a);
if(aa[i-1][j]==0&&!yes)
{
fun(aa,i-1,j);
if(yes)
{x[n][0]=i,x[n++][1]=j;return;}
}
fun1(aa,a);
if(aa[i-1][j+1]==0&&!yes)
{
fun(aa,i-1,j+1);
if(yes)
{x[n][0]=i,x[n++][1]=j;return;}
}
fun1(aa,a);
if(aa[i+1][j-1]==0&&!yes)
{
fun(aa,i+1,j-1);
if(yes)
{x[n][0]=i,x[n++][1]=j;return;}
}
fun1(aa,a);
if(aa[i][j-1]==0&&!yes)
{
fun(aa,i,j-1);
if(yes)
{x[n][0]=i,x[n++][1]=j;return;}
}
fun1(aa,a);
if(aa[i-1][j-1]==0&&!yes)
{
fun(aa,i-1,j-1);
if(yes)
{x[n][0]=i,x[n++][1]=j;return;}
}
}
void begain(int (*t)[N])
{
int i,j;
system(cls);
randomize();
for(i=0;i<N;i++)
{
for(j=0;j<N;j++)
{
if(i==0||i==N-1||j==0||j==N-1)
t[i][j]=1;
else if(i==1&&j==1||i==N-2&&j==N-2)
t[i][j]=0;
else
t[i][j]=random(2);
}
}
}
void pr(int (*t)[N],int nn)
{
int i,j,ii;
textcolor(RED);
gotoxy(1,1);
for(i=0;i<N;i++)
{
for(j=0;j<N;j++)
{
if(nn!=1)
printf(%2d,t[i][j]);
else
{
for(ii=0;ii<n;ii++)
{
if(x[ii][0]==i&&x[ii][1]==j)
{
cprintf(%2d,t[i][j]);
break;
}
}
if(ii<n)
continue;
if(i==N-2&&j==N-2)
cprintf( 0);
else
printf(%2d,t[i][j]);
}
}
printf(\n);
}
}
void win(int (*t)[N])
{
int i,j,ii,jj;
for(i=0;i<n-1;i++)
for(j=i+1;j<n;j++)
if(x[j][0]==x[i][0]&&x[j][1]==x[i][1])
{
for(jj=j,ii=i;jj<n;jj++,ii++)
{x[ii][0]=x[jj][0];x[ii][1]=x[jj][1];}
n=n-(j-i);
}
printf(\nThe way is:\n);
for(i=n-1;i>=0;i--)
printf(%3d%3d->,x[i][0],x[i][1]);
printf(%3d%3d\n,N-2,N-2);
t[1][1]=0;
pr(t,1);
}
void lose()
{
printf(\nNot find way!\n);
}
⑵ 简单的迷宫算法
用python递归求解
dirs=[(0,1),(1,0),(0,-1),(-1,0)] #当前位置四个方向的偏移量
path=[] #存找到的路径
def mark(maze,pos): #给迷宫maze的位置pos标"2"表示“倒过了”
maze[pos[0]][pos[1]]=2
def passable(maze,pos): #检查迷宫maze的位置pos是否可通行
return maze[pos[0]][pos[1]]==0
def find_path(maze,pos,end):
mark(maze,pos)
if pos==end:
print(pos,end=" ") #已到达出口，输出这个位置。成功结束
path.append(pos)
return True
for i in range(4): #否则按四个方向顺序检查
nextp=pos[0]+dirs[i][0],pos[1]+dirs[i][1]
#考虑下一个可能方向
if passable(maze,nextp): #不可行的相邻位置不管
if find_path(maze,nextp,end):#如果从nextp可达出口，输出这个位置，成功结束
print(pos,end=" ")
path.append(pos)
return True
return False
def see_path(maze,path): #使寻找到的路径可视化
for i,p in enumerate(path):
if i==0:
maze[p[0]][p[1]] ="E"
elif i==len(path)-1:
maze[p[0]][p[1]]="S"
else:
maze[p[0]][p[1]] =3
print("\n")
for r in maze:
for c in r:
if c==3:
print('\033[0;31m'+"*"+" "+'\033[0m',end="")
elif c=="S" or c=="E":
print('\033[0;34m'+c+" " + '\033[0m', end="")
elif c==2:
print('\033[0;32m'+"#"+" "+'\033[0m',end="")
elif c==1:
print('\033[0;;40m'+" "*2+'\033[0m',end="")
else:
print(" "*2,end="")
print()
if __name__ == '__main__':
maze=[[1,1,1,1,1,1,1,1,1,1,1,1,1,1],\
[1,0,0,0,1,1,0,0,0,1,0,0,0,1],\
[1,0,1,0,0,0,0,1,0,1,0,1,0,1],\
[1,0,1,0,1,1,1,1,0,1,0,1,0,1],\
[1,0,1,0,0,0,0,0,0,1,1,1,0,1],\
[1,0,1,1,1,1,1,1,1,1,0,0,0,1],\
[1,0,1,0,0,0,0,0,0,0,0,1,0,1],\
[1,0,0,0,1,1,1,0,1,0,1,1,0,1],\
[1,0,1,0,1,0,1,0,1,0,1,0,0,1],\
[1,0,1,0,1,0,1,0,1,1,1,1,0,1],\
[1,0,1,0,0,0,1,0,0,1,0,0,0,1],\
[1,1,1,1,1,1,1,1,1,1,1,1,1,1]]
start=(1,1)
end=(10,12)
find_path(maze,start,end)
see_path(maze,path)
⑶ 算法设计：求广度优先搜索解决迷宫问题的思路
广度优先一般就是使用队列，创建一个队列，然后开始搜索起始点四周的结点加入队列，搜完一个结点后作出标记避免重复搜索，接着出队列继续搜索，知道搜索完队列内的结点。
广度优先就是先搜索四周的慢慢向四周扩展。