1. 簡單的迷宮演算法
用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)
2. 迷宮的演算法
BFS搜索
利用隊列對n個方向進行訪問。
3. 迷宮演算法 上下左右 優先順序問題
迷宮一般採用遞歸演算法，而且出口位置在演算法開始時候是不知道的吧。而且迷宮的出口也不會固定到哪一個方向。如果採用枚舉方法一般是按順時針或者逆時針找，這樣才可以用循環來做，如果採用優先，只能將每個方向定位，設一個常量，那樣的話每次遞歸都要判斷一下，非常麻煩，估計還比不用優先還慢一些。
4. 迷宮演算法
#include<stdio.h>
#include<stdlib.h>
#define M 15
#define N 15
struct mark //定義迷宮內點的坐標類型
{
int x;
int y;
};
struct Element //"戀"棧元素，嘿嘿。。
{
int x,y; //x行,y列
int d; //d下一步的方向
};
typedef struct LStack //鏈棧
{
Element elem;
struct LStack *next;
}*PLStack;
/*************棧函數****************/
int InitStack(PLStack &S)//構造空棧
{
S=NULL;
return 1;
}
int StackEmpty(PLStack S)//判斷棧是否為空
{
if(S==NULL)
return 1;
else
return 0;
}
int Push(PLStack &S, Element e)//壓入新數據元素
{
PLStack p;
p=(PLStack)malloc(sizeof(LStack));
p->elem=e;
p->next=S;
S=p;
return 1;
}
int Pop(PLStack &S,Element &e) //棧頂元素出棧
{
PLStack p;
if(!StackEmpty(S))
{
e=S->elem;
p=S;
S=S->next;
free(p);
return 1;
}
else
return 0;
}
/***************求迷宮路徑函數***********************/
void MazePath(struct mark start,struct mark end,int maze[M][N],int diradd[4][2])
{
int i,j,d;int a,b;
Element elem,e;
PLStack S1, S2;
InitStack(S1);
InitStack(S2);
maze[start.x][start.y]=2; //入口點作上標記
elem.x=start.x;
elem.y=start.y;
elem.d=-1; //開始為-1
Push(S1,elem);
while(!StackEmpty(S1)) //棧不為空 有路徑可走
{
Pop(S1,elem);
i=elem.x;
j=elem.y;
d=elem.d+1; //下一個方向
while(d<4) //試探東南西北各個方向
{
a=i+diradd[d][0];
b=j+diradd[d][1];
if(a==end.x && b==end.y && maze[a][b]==0) //如果到了出口
{
elem.x=i;
elem.y=j;
elem.d=d;
Push(S1,elem);
elem.x=a;
elem.y=b;
elem.d=886; //方向輸出為-1 判斷是否到了出口
Push(S1,elem);
printf("\n0=東 1=南 2=西 3=北 886為則走出迷宮\n\n通路為:(行坐標,列坐標,方向)\n");
while(S1) //逆置序列 並輸出迷宮路徑序列
{
Pop(S1,e);
Push(S2,e);
}
while(S2)
{
Pop(S2,e);
printf("-->(%d,%d,%d)",e.x,e.y,e.d);
}
return; //跳出兩層循環，本來用break,但發現出錯，exit又會結束程序，選用return還是不錯滴o(∩_∩)o...
}
if(maze[a][b]==0) //找到可以前進的非出口的點
{
maze[a][b]=2; //標記走過此點
elem.x=i;
elem.y=j;
elem.d=d;
Push(S1,elem); //當前位置入棧
i=a; //下一點轉化為當前點
j=b;
d=-1;
}
d++;
}
}
printf("沒有找到可以走出此迷宮的路徑\n");
}
/*************建立迷宮*******************/
void initmaze(int maze[M][N])
{
int i,j;
int m,n; //迷宮行,列
printf("請輸入迷宮的行數 m=");
scanf("%d",&m);
printf("請輸入迷宮的列數 n=");
scanf("%d",&n);
printf("\n請輸入迷宮的各行各列:\n用空格隔開,0代表路,1代表牆\n",m,n);
for(i=1;i<=m;i++)
for(j=1;j<=n;j++)
scanf("%d",&maze[i][j]);
printf("你建立的迷宮為o(∩_∩)o...\n");
for(i=0;i<=m+1;i++) //加一圈圍牆
{
maze[i][0]=1;
maze[i][n+1]=1;
}
for(j=0;j<=n+1;j++)
{
maze[0][j]=1;
maze[m+1][j]=1;
}
for(i=0;i<=m+1;i++) //輸出迷宮
{
for(j=0;j<=n+1;j++)
printf("%d ",maze[i][j]);
printf("\n");
}
}
void main()
{
int sto[M][N];
struct mark start,end; //start,end入口和出口的坐標
int add[4][2]={{0,1},{1,0},{0,-1},{-1,0}};//行增量和列增量 方向依次為東西南北
initmaze(sto);//建立迷宮
printf("輸入入口的橫坐標,縱坐標[逗號隔開]\n");
scanf("%d,%d",&start.x,&start.y);
printf("輸入出口的橫坐標,縱坐標[逗號隔開]\n");
scanf("%d,%d",&end.x,&end.y);
MazePath(start,end,sto,add); //find path
system("PAUSE");
}
5. 演算法設計：求廣度優先搜索解決迷宮問題的思路
廣度優先一般就是使用隊列，創建一個隊列，然後開始搜索起始點四周的結點加入隊列，搜完一個結點後作出標記避免重復搜索，接著出隊列繼續搜索，知道搜索完隊列內的結點。
廣度優先就是先搜索四周的慢慢向四周擴展。
6. 一般迷宮游戲用到什麼演算法
狀壓DP，或者記憶化搜索。
一般的就是F[i,j,k]表示站在i,j點，當前已經得到了k的狀態。然後轉移。
7. 寫程序，用演算法找迷宮的路徑（隨意路徑或者最短路徑）
8. 求迷宮演算法，c++語言
/*地圖路徑求解程序，用VC++編寫的，在TC下運行可能有問題的。
問題的情況可能是：不認識false和true，去掉下面定義的兩行前面的「/*」即可定義他們
也可能有變數名稱過長的錯誤，如果是那樣，就麻煩你自己修改變數名吧，把所有的變數名稱替換為少於8位元組的*/
#include<stdio.h>
#include<stdlib.h>
#define ROW 9/*定義行數*/
#define COL 13/*定義列數*/
///*#define false 0/*定義false為0，如果在C語言中需要這個，就把前面的「/*」去掉*/
///*#define true 1/*定義true為1，如果在C語言中需要這個，就把前面的「/*」去掉*/
typedef struct RowAndColPath{
int r;
int c;
}RowAndColPath;/*定義結構體實現走步過程的記錄*/
int Move[4][2]={{0,1},{1,0},{-1,0},{0,-1}};/*4個方向*/
RowAndColPath path[ROW*COL];/*走動過程的記錄*/
bool ResultFlag=false;/*找到解的標志*/
bool GettingPath(int step,int CurrentRow,int CurrentCol,int ResultRow,int ResultCol,int MapWay[][COL]);/*遞歸求解方法*/
void main()
{
int MapWay[ROW][COL]={
{1,1,1,1,1,1,1,1,0,1,1,1,1},
{0,0,0,1,1,0,0,0,0,1,1,1,1},
{1,1,0,1,1,1,1,1,0,0,1,1,1},
{1,1,0,0,0,0,1,1,1,0,1,1,1},
{1,1,0,1,1,0,0,0,0,0,0,0,1},
{1,1,0,0,1,1,1,1,1,1,1,0,1},
{1,1,1,0,0,0,0,0,0,1,1,0,1},
{1,1,1,0,1,1,1,1,0,0,0,0,1},
{1,1,1,0,0,0,1,1,1,1,1,1,1}};/*定義地圖*/
int CurrentRow=1,CurrentCol=0,ResultRow=0,ResultCol=8;/*定義初始和結束位置*/
path[0].r=CurrentRow;
path[0].c=CurrentCol;/*初始位置進入歷史的第一步*/
if(GettingPath(1,CurrentRow,CurrentCol,ResultRow,ResultCol,MapWay))/*如果走動成功*/
printf("恭喜！查找成功！\n");
else
printf("抱歉，查找失敗！\n");
}
bool GettingPath(int step,int CurrentRow,int CurrentCol,int ResultRow,int ResultCol,int MapWay[][COL])
{
int i,j;
for(i=0;i<4;i++)/*依次對4個方向搜索*/
{
if(ResultFlag)
return true;
CurrentRow+=Move[i][0];
CurrentCol+=Move[i][1];/*先按該方向前進一步*/
if((CurrentRow>=0)&&(CurrentRow<ROW)&&(CurrentCol>=0)&&(CurrentRow<COL))/*如果還在地圖內部*/
{
if(MapWay[CurrentRow][CurrentCol]==0)/*下一步可以走*/
{
for(j=0;j<step;j++)/*判斷是不是重復了以前走過的路*/
{
if((path[j].r==CurrentRow)&&(path[j].c==CurrentCol))
break;
}
if(j==step)/*如果沒有走過這個點，就走*/
{
path[step].r=CurrentRow;
path[step].c=CurrentCol;/*計入該步*/
step++;
if((CurrentRow==ResultRow)&&(CurrentCol==ResultCol))/*如果已到達目的地*/
{
ResultFlag=true;
printf("路徑如下：\n\n");
for(j=0;j<step;j++)
printf("第 %d 步：\t%d\t%d\n",j,path[j].r,path[j].c);
return true;
}
else
{
if(step>=ROW*COL)/*如果已經走遍了地圖，就宣布失敗*/
return 0;
if(!ResultFlag)
GettingPath(step,CurrentRow,CurrentCol,ResultRow,ResultCol,MapWay);/*沒有到達目的，繼續走*/
}
}
else/*如果已經走過這一點，退回去*/
{
CurrentRow-=Move[i][0];
CurrentCol-=Move[i][1];;
}
}
else/*如果該點不可走，退回去*/
{
CurrentRow-=Move[i][0];
CurrentCol-=Move[i][1];;
}
}
else/*如果該步出地圖了，退回去*/
{
CurrentRow-=Move[i][0];
CurrentCol-=Move[i][1];;
}
}
if(ResultFlag)
return true;
return false;/*無路可走*/
}
9. 如何用C語言實現求迷宮的最短路徑
#include<stdio.h>
#include<stdlib.h>
#define M 8
#define N 8
#define Max 100
int mg[M+2][N+2]= //定義迷宮，0表示能走的塊，1表示不能走，在外圍加上一圈不能走的塊
{
{1,1,1,1,1,1,1,1,1,1},
{1,0,0,1,0,0,0,1,0,1},
{1,0,0,1,0,0,0,1,0,1},
{1,0,0,0,0,1,1,0,0,1},
{1,0,1,1,1,0,0,0,0,1},
{1,0,0,0,1,0,0,0,0,1},
{1,0,1,0,0,0,1,0,0,1},
{1,0,1,1,1,0,1,1,0,1},
{1,1,0,0,0,0,0,0,0,1},
{1,1,1,1,1,1,1,1,1,1}
};
struct
{
int i,j; //塊的位置
int pre; //本路徑中上一塊在隊列中的下標
}Qu[Max];
int front=-1,rear=-1;
void print(int n);
int mgpath(int xi,int yi,int xe,int ye) //搜索演算法
{
int i,j,find=0,di;
rear++;
Qu[rear].i=xi;
Qu[rear].j=yi;
Qu[rear].pre=-1;
mg[1][1]=-1;
while(front<=rear&&!find)
{
front++;
i=Qu[front].i;
j=Qu[front].j;
if(i==xe&&j==ye)
{
find=1;
print(front);
return(1);
}
for(di=0;di<4;di++)
{
switch(di) //四個方向
{
case 0:i=Qu[front].i-1;j=Qu[front].j;break;
case 1:i=Qu[front].i;j=Qu[front].j+1;break;
case 2:i=Qu[front].i+1;j=Qu[front].j;break;
case 3:i=Qu[front].i;j=Qu[front].j-1;break;
}
if(mg[i][j]==0)
{
rear++;
Qu[rear].i=i;
Qu[rear].j=j;
Qu[rear].pre=front;
mg[i][j]=-1; //避免死循環
}
}
}
return 0;
}
void print(int n) //輸出 路徑演算法
{
int k=n,j,m=1;
printf("\n");
do //將輸出的路徑上的所有pre改為-1
{
j=k;
k=Qu[k].pre;
Qu[j].pre=-1;
}while(k!=0);
printf("迷宮最短路徑如下：\n");
k=0;
while(k<Max)
{
if(Qu[k].pre==-1)
{
printf("\t(%d,%d)",Qu[k].i,Qu[k].j);
if(m%5==0)
printf("\n");
m++;
}
k++;
}
printf("\n");
}
int main()
{
mgpath(1,1,M,N);
system("pause");
return 0;
}
10. 電腦鼠走迷宮中迷宮搜索演算法都有哪些
左手法則、右手法則，中左、中右法則，中心演算法，洪水演算法，A*演算法，蟻群演算法，遺傳演算法等