演算法分析與設計迷宮演算法
1. 試設計迷宮求解演算法:迷宮是一個m行n列的0-1矩陣,其中0表示無障礙,1表示有障礙
假設8個方位被簡單定義為 char a[8];
int path(point *location)
{
if(「location不為出口」&&「location.a[0]未涉足過」)
path(location->a[0]);
else if(「location不為出口」&&「location.a[1]未涉足過」)
path(location->a[0]);
else if(「location不為出口」&&「location.a[2]未涉足過」)
path(location->a[0]);
` ````````````````````
``````````
``````
``
else return 0;
}
這是一個迭代過程，需要對每一個方位的位置都遍歷一遍，也是一個深度優先的遍歷過程。
我在這只給lz一個示意，具體的演算法在《數據結構》的書上基本都有，蠻經典的。希望能對lz有所幫組。
加油！
2. 數據結構 迷宮問題演算法
//迷宮求解（自定義一個2維矩陣作為地圖）
void Labyrinth()
{
printf("自定義迷宮矩陣：\n");
int a[10][10];
int i,j;
for(i=0;i<10;i++)
for(j=0;j<10;j++)
scanf("%d",&a[i][j]);
printf("\n");
coordinate *Laby = new coordinate[100];
int n=1;
int x,y;
Laby[1].x=x=1;
Laby[1].y=y=6;
Laby[1].step=1;
a[1][6]=2;
SqStack S;
InitStack(S);
Push(S,0);
Push(S,1);
i=1;
while(GetTop(S))
{
if(a[x][y]==100)
{
printf("找到終點了!!!\n");
break;
}
i++;
if(n==1)
a[x][y]=i;
if(a[x][y-1]==1||a[x-1][y]==100)
{
Push(S,i);
Laby[i].x=x;
Laby[i].y=y=y-1;
Laby[i].step=i;
n=1;
continue;
}
else if(a[x-1][y]==1||a[x-1][y]==100)
{
Push(S,i);
Laby[i].x=x=x-1;
Laby[i].y=y;
Laby[i].step=i;
n=1;
continue;
}
else if(a[x][y+1]==1||a[x][y+1]==100)
{
Push(S,i);
Laby[i].x=x;
Laby[i].y=y=y+1;
Laby[i].step=i;
n=1;
continue;
}
else if(a[x+1][y]==1||a[x+1][y]==100)
{
Push(S,i);
Laby[i].x=x=x+1;
Laby[i].y=y;
Laby[i].step=i;
n=1;
continue;
}
else
{
Pop(S,i);
x=Laby[i].x;
y=Laby[i].y;
a[x][y]=-1;
n=0;
}
}
if(!GetTop(S))
printf("沒有找到出路!\n");
for(i=0;i<10;i++)
{
for(j=0;j<10;j++)
printf("%d ",a[i][j]);
printf("\n");
}
}
我沒有給出棧的代碼，你自己應該有吧！
具體迷宮演算法 就是如此 僅供參考
3. 求走迷宮的演算法！（計算機的演算法）（編程也可以
我的思路：
按照人類走迷宮的方法，貼著左邊走，左邊有路就向左走，左邊沒路向前走，左邊前面都沒路向右走
機器人的應該是：1.判斷左邊是否有牆，無牆：機器人左轉，前進一步，繼續判斷左。。
2.左邊有牆，則判斷前方是否有牆，無則向前一步，跳回第一步
3.前方有牆（此時狀態是左有牆，前有牆），則向機器人右轉，跳回第一步
另外有個前提條件，機器人轉彎需要原地轉，有轉彎半徑的肯定不行。
還有個問題，就是機器人自己不知道自己已經從迷宮出來了，會一直走。。
4. 迷宮問題求解的實現演算法
源程序：
//base.h
#include
#include
#include
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int Status;
//stack.h
#include "base.h"
#define INIT_SIZE 100 //存儲空間初始分配量
#define INCREMENT 10 //存儲空間分配增量
typedef struct{ //迷宮中r行c列的位置
int r;
int c;
}PostType;
typedef struct{
int ord; //當前位置在路徑上的序號
PostType seat;//當前坐標
int di; //往下一坐標的方向
}SElemType; //棧元素類型
typedef struct{
SElemType* base;//棧基址,構造前銷毀後為空
SElemType* top;//棧頂
int stackSize; //棧容量
}Stack; //棧類型
Status InitStack(Stack &S){ //構造空棧s
S.base=(SElemType*)malloc(INIT_SIZE *sizeof(SElemType));
if(!S.base)
exit(OVERFLOW);//存儲分配失敗
S.top=S.base;
S.stackSize=INIT_SIZE;
return OK;
}//InitStack
Status StackEmpty(Stack S){
//若s為空返回TRUE,否則返回FALSE
if(S.top==S.base)
return TRUE;
return FALSE;
}//StackEmpty
Status Push(Stack &S,SElemType e){
//插入元素e為新的棧頂元素
if(S.top-S.base >=S.stackSize){//棧滿，加空間
S.base=(SElemType *)realloc(S.base,(S.stackSize+INCREMENT)*sizeof(SElemType));
if(!S.base)
exit(OVERFLOW); //存儲分配失敗
S.top=S.base+S.stackSize;
S.stackSize+=INCREMENT;
}
*S.top++=e;
return OK;
}//push
Status Pop(Stack &S,SElemType &e){//若棧不空刪除棧//頂元素用e返回並返回OK，否則返回ERROR
if(S.top==S.base)
return ERROR;
e=*--S.top;
return OK;
}//Pop
Status DestroyStack(Stack &S){//銷毀棧S,
free(S.base);
S.top=S.base;
return OK;
5. 迷宮演算法的修改編寫
#include<stdio.h>
#include<string.h>
int dir[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
int map[10][10], n=5;
int b[1000],t=0;
bool ok(int x)
{
return x>=1&&x<=n;
}
void DFS(int x,int y)
{
int i,tx,ty;
b[t]=t;
t++;
map[x][y]=0;
for(i=0;i<4;i++)
{
tx=x+dir[i][0];
ty=y+dir[i][1];
if(!ok(tx)||!ok(ty)||map[tx][ty]==0)
{
continue;
}
DFS(tx,ty);
}
}
void genMat(){}
int main()
{
int i;
genMat();//這里調用你的演算法生成5*5 的矩陣
DFS(1,1);
for(i=0;i<t;i++)printf("%d ",b[i]);
puts("");
return 0;
}
6. 羅密歐與朱麗葉的迷宮問題 演算法分析與設計
這里已經有了：
http://apps.hi..com/share/detail/12714033
走完迷宮所有的格子,並且轉彎次數最少..
在最後找到朱麗葉.
#include<iostream>
using namespace std;
int dir[9][2]={{0,0},{0,1},{0,-1},{1,0},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1}};
int count;
int dirs,best;
int board[20][20],bestw[20][20];
int m,n,k;
int sx,sy,ex,ey;
bool comp(int x,int y)
{
if(x>0&&x<=n&&y>0&&y<=m&&board[x][y]==0)
return true;
else return false;
}
void save()
{
int i,j;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
bestw[i][j]=board[i][j];
}
void search(int dep,int x,int y,int di)
{
if(dep==m*n-k&&x==ex&&y==ey&&dirs<=best)
{
if(dirs<best)
{
best=dirs;
count=1;
save();
}
else count++;
return;
}
if(dep==m*n-k||x==ex&&y==ey||dirs>best) return;
else
{
for(int i=1;i<=8;i++)
if(comp(x+dir[i][0],y+dir[i][1]))
{
board[x+dir[i][0]][y+dir[i][1]]=dep+1;
if(di!=i) dirs++;
search(dep+1,x+dir[i][0],y+dir[i][1],i);
if(di!=i) dirs--;
board[x+dir[i][0]][y+dir[i][1]]=0;
}
}
}
int main()
{
cin>>n>>m>>k;
int i,j;
int c,d;
memset(board,0,sizeof(board));
for(i=0;i<k;i++)
{
cin>>c>>d;
board[c][d]=-1;
}
cin>>sx>>sy;
cin>>ex>>ey;
board[sx][sy]=1;
best=m*n;
dirs=-1;
/***********************
for(i=0;i<n;i++)
{
for(j=0;j<m;j++)
cout<<board[i][j]<<" ";
cout<<endl;
}
***********************/
search(1,sx,sy,0);
cout<<best<<endl;
cout<<count<<endl;
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
cout<<bestw[i][j]<<" ";
cout<<endl;
}
}
來自: http://hi..com/dearshawn/blog/item/a4a32eeb2e8277d9d539c90b.html
7. 迷宮問題演算法設計！！急急急（c語言）
額，又是課程設計。。。
迷宮類演算法，用棧，隊列來做。不過一般來隊列，因為隊列能夠在較短時間內求出最短路徑。
在網上搜下，很多的。。
你的要求很難達到。。。
8. 迷宮演算法問題
棧走到底也可以回過頭來繼續探索啊，要不怎麼叫深度【遍歷】。
9. 迷宮演算法
#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");
}