⑴ 迷宮求解的非遞歸演算法
迷宮求解
任務：可以輸入一個任意大小的迷宮數據，用非遞歸的方法求出一條走出迷宮的路徑，並將路徑輸出；
在資料中請寫明：存儲結構、基本演算法（可以使用程序流程圖）、源程序、測試數據和結果、演算法的時間復雜度、另外可以提出演算法的改進方法；
拜託高手大家些們，我寫了個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)
⑶ 演算法設計：求廣度優先搜索解決迷宮問題的思路
廣度優先一般就是使用隊列，創建一個隊列，然後開始搜索起始點四周的結點加入隊列，搜完一個結點後作出標記避免重復搜索，接著出隊列繼續搜索，知道搜索完隊列內的結點。
廣度優先就是先搜索四周的慢慢向四周擴展。