A. c語言中用棧實現迷宮問題
#include
#define MAXSIZE 100
using namespace std;
struct stack{
int iway;
int jway;
int dire;
};
stack maze[MAXSIZE];
int top;
int map[14][28]={{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1},
{1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,1,1,1,0,0,0,0,0,1,1,1,1,1},
{1,1,0,0,1,0,0,0,0,0,0,0,0,0,0,1,1,1,0,0,0,0,0,0,0,0,0,1},
{1,0,0,0,0,0,0,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1},
{1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1},
{1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,1,1,0,0,1,1,0,0,1},
{1,0,0,0,0,0,0,0,1,1,1,0,0,0,1,0,0,0,0,1,1,0,1,1,1,1,0,1},
{1,0,0,0,0,0,0,0,1,1,1,0,1,1,1,1,0,0,0,1,1,0,1,1,1,1,0,1},
{1,0,0,0,0,0,0,0,1,1,1,0,0,0,1,0,0,0,0,1,1,0,0,1,1,0,0,1},
{1,0,0,0,0,0,0,0,1,1,1,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,1},
{1,0,0,0,0,1,1,0,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1},
{1,0,0,0,0,1,1,0,1,1,1,0,0,0,0,0,0,0,1,1,1,1,0,0,0,0,0,1},
{1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,0,0,0,0,0,1},
{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}};
void findway(int xS,int yS,int xE,int yE)
{
top=0;
maze[top].iway=xS;
maze[top].jway=yS;
map[xS][yS]=-1;
int i,j,di,find;
while(top>-1)
{
i=maze[top].iway;
j=maze[top].jway;
di=maze[top].dire;
if(i==xE&&j==yE)
{
cout<<"***********************************\n";
cout<<"path"<<":"<<endl;
cout<<"("<<maze[0].iway<<","<<maze[0].jway<<")";
for(int val=1;val<top+1;val++)
{
cout<("<<maze[val].iway<<","<<maze[val].jway<<")";
if((val+1)%5==0)
cout<<endl;
}
cout<<endl;
cout<<"***********************************\n";
return;
}
find=0;
while(find==0&&di<4)
{
di++;
switch(di)
{
case(0):i=maze[top].iway;
j=maze[top].jway+1;
break;
case(1):i=maze[top].iway;
j=maze[top].jway-1;
break;
case(2):i=maze[top].iway+1;
j=maze[top].jway;
break;
case(3):i=maze[top].iway-1;
j=maze[top].jway;
break;
}
if(map[i][j]==0)
{
find=1;
}
}
if(find==1)
{
maze[top].dire=di;
top++;
maze[top].iway=i;
maze[top].jway=j;
maze[top].dire=-1;
map[i][j]=-1;
}
else
{
map[maze[top].iway][maze[top].jway]=0;
top--;
}
}
}
int main()
{
for(int i=0;i<14;i++) //迷宮圖形化輸出
{
for(int j=0;j<28;j++)
{
if(map[i][j]==1)
cout<<"■";
else cout<<"□";
}
cout<<endl;
}
int xStart,yStart,xEnd,yEnd;
cout<<"請輸入迷宮起點坐標，用空格隔開(左上角坐標為(0,0)):";
cin>>xStart>>yStart;
cout<<"請輸入迷宮終點坐標，用空格隔開(右上角坐標為(13,27)):";
cin>>xEnd>>yEnd;
findway(xStart,yStart,xEnd,yEnd);
return 0;
}
滿意請採納！
B. 迷宮問題演算法設計！！急急急（c語言）
額，又塵配是課程設計。。。
迷宮類演算法，用棧，隊列來做檔兄胡。不過一般來隊列，因為隊列能夠在較短時間內求出最短路徑。
在網上行攔搜下，很多的。。
你的要求很難達到。。。
C. 數據結構迷宮問題（c語言）
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<time.h>
int m,n,num,map[101][101],f[101][101],a[101],b[101],d[2][4]={0,-1,0,1,-1,0,1,0},ans,flag;
void maze()
{
int i,j;
time_t t;
srand(time(&t));
for(i=0;i<m;i++)
for(j=0;j<n;j++)
{
map[i][j]=rand()%2;
if(map[i][j])
num++;
}
if(num<m*n/2)
{
for(i=0;i<m;i++)
for(j=0;j<n;j++)
if(!map[i][j])
map[i][j]+=rand()%2;
}
map[0][0]=1;
map[m-1][n-1]=1;
}
void print()
{
int i,j;
for(i=0;i<m;i++)
for(j=0;j<n;j++)
{
printf("%d ",map[i][j]);
if(j==n-1)puts("");
}
}
void dfs(int x,int y)
{
int i,tx,ty;
if(!flag)
return;
for(i=0;i<4;i++)
{
tx=x+d[0][i];
ty=y+d[1][i];
if(!f[tx][ty]&&tx>=0&&ty>=0&&tx<m&&ty<n&&map[tx][ty])
{
f[tx][ty]=1;
a[ans]=tx;
b[ans++]=ty;
if(tx+ty==0)
{
printf("(%d,%d)\n",m,n);
for(flag=i=0;i<ans;i++)
printf("(%d,%d)\n",a[i]+1,b[i]+1);
return;
}
dfs(tx,ty);
f[tx][ty]=0;
ans--;
}
}
}
int main()
{
while(scanf("%d%d",&m,&n),m+n)
{
memset(f,0,sizeof(f));
num=ans=0;
flag=1;
maze();
print();
dfs(m-1,n-1);
if(flag)
puts("There is no path");
}
return 0;
}
D. 數據結構演算法（c語言） 迷宮求解
注釋非常詳細，希望對你有所幫助。
#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還是不錯滴
}
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; //迷宮行,列 [/M]
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("你建立的迷宮為(最外圈為牆)...\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}};//行增量和列增量 方向依次為東西南北 [/M]
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");
}
測試數據，演算法復雜度你就自己來寫吧，如果你連這都不自己做，那你一定是在應付作業。勸你還是自己運行測試一下吧，免得答辯時老師問你，什麼都不知道，那你就悲劇了。祝你好運！！
E. 數據結構C語言版迷宮問題
剛學都這樣，想當初我學習的時候連一個單鏈表的逆置，都要理解半天。編程就是把實際問題給抽象成數學或非數學模型，結合數據的表示，再找到解決的方法。別忘了，學習數據結構是為了更好的操作數據。
思路：
首先，迷宮如何用計算機語言表示？一般用二維數組。0表示牆，1表示路。
其次，其次就是如何從迷宮中走出來了。結合堆棧，進行搜索。
你可以嘗試著對問題進行分層，然後逐步細化來解決。
如果你要解決一個別人給的走迷宮的問題，同樣還是要這樣，首先把別人給的迷宮在計算機中表示出來，其次結合數據結構所學的知識，找到通路，（關於結合數據結構的知識就看你自己的了，關鍵是對堆棧的了解）。
關於你說的，先看別人的程序，找到思路後自己才能編程問題。我看你是操之過急了，你得明白，知識的學習，首先就是會模仿，等你對整個課程有了系統的認識，你才會有自己的解題思路。創新是在有基礎的前提下進行的。別人的東西，試著理解，畢竟許多東西單憑我們自己是不太可能想出來的，就像kmp演算法一樣（你應該馬上就會學到）。
第一章說過，研究數據間的關系的目的是為了更好的操作數據，迷宮問題，可以說是一類「搜索」問題，更強調的是演算法，即在精通堆棧的基礎上想出一個利用堆棧對迷宮進行搜索的辦法。而堆棧，則是基礎，堆棧的操作就那麼幾個，學完馬上就會用。關鍵是如何運用三種程序設計方法再結合某些數據結構設計出一個演算法。一步一步來吧。
對了，給你一個問題考慮考慮，「不用任何輔助變數」編寫一個程序，逆置一個字元串試試。只給你一個參數：該參數就是指向字元串的指針。
你的最後問題問的就有點沒頭緒了，學習的過程並不是你想的那樣的，不見得數據結構學完之後就能編寫高質量程序，寫程序和看程序是相輔相成的，寫而不學則怠，學而不寫則罔。可以嘗試的寫寫，自己找不到思路可以看看別人是怎麼想的，自己多做做總結。
F. C語言：迷宮，求程序，快哭了！好虐。。。
輸入這段就不用寫了吧。比較簡單
A 輸入迷宮
用2維數組把這個 迷宮存下來就行了。 牆用0表示 路用1表示。 或者直接用字元的2維數組也行。設為公共變數 migong[m][m] 用公共變數存 m
B 走通判定 (這里以一個迷宮為例，多個迷宮的話 輸入那邊處理一下就好了，反正中心思想就是1個迷宮用一個2維數組存)
是否能走通的判定。 用迭代法
1 判定周圍是否有e(因為e在右下角 只用判斷下方和右方就可以了)
2 沒有向右走
3 右是牆的話向下走
4 下是牆的話向左走
5 左是牆的話向上走。
bool findway(int startx,int,starty)
{
int end = m - 1;
if(x + 1 == end && y == end || x == end && y + 1 == end )
{
return true; //可以走通 返回YES
}
else if (x + 1 < end && migong[x + 1][y] != '#') //當前點不處於最右側 且右側點不為牆的時候
{
findway(startx + 1,starty); //右移
}
else if(y + 1 < end && migong[x][y+1] !='#' ) //當前點不處於最下側 且下側點不為牆的時候
{
findway(startx,starty + 1); //下移
}
............................//按照這個思路做 以下省略
}
然後主函數中調用 findway(0,0) 就OK了。
寫得比較簡單，不好意思。
G. 急求：C語言實現的迷宮問題代碼！
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
struct node
{
int sign;//標識,0什麼都不在,1在open中,2在closed中
int flag;//標志位 0/1,0可以走,1不可以走
int f,g,h;//判舉春斷函數
int x,y;//坐標
int old;//正返耐是否old節點,0非,1是
};
struct link
{
node fnode;
link *next;
link *pri;
};
link *open,*closed,*bestnode,*successor,*p,*q,*r,*s;
int maze_flag[7][7]={ {0,1,0,0,0,0,0},
{0,1,0,1,0,1,0},
{0,1,0,0,0,1,0},
{0,1,0,1,0,1,0},
{0,0,0,1,0,0,0},
{1,1,0,1,0,1,0},
{0,0,0,0,0,1,0}};//表示迷宮的數組,0可以走,1不可以走
node maze[7][7];
int judge(node n)//判斷函數,判斷n節點是否可以走
{
if(n.flag==1)
return(1);
else
return(0);
}
void in_open(node n)//將n節點放入open表
{
p=open;
while(p->next!=open)
{
if(n.f>=p->fnode.f)
{
p->next->pri=(link *)malloc(sizeof(link));
p->next->pri->pri=p;
p=p->next;
p->pri->next=p;
p->pri->pri->next=p->pri;
p=p->pri;
p->fnode.flag=n.flag;
p->fnode.f=n.f;
p->fnode.g=n.g;
p->fnode.h=n.h;
p->fnode.x=n.x;
p->fnode.y=n.y;
p->fnode.old=n.old;
p->fnode.sign=n.sign=1;
}
else
p=p->next;
}
open->pri=(link *)malloc(sizeof(link));
open->pri->pri=p;
open->pri->next=open;
p->next=open->pri;
p=p->next;
p->fnode.flag=n.flag;
p->fnode.f=n.f;
p->fnode.g=n.g;
p->fnode.h=n.h;
p->fnode.x=n.x;
p->fnode.y=n.y;
p->fnode.old=n.old;
p->fnode.sign=n.sign=1;
}
void out_open(node n)//將n節點從open表中移出
{
p=open;
while(p->next!=open)
{
if(n.f=p->fnode.f)
{
link *p1;
p1=p->next;
p->next=p->next->next;
p->next->pri=p;
free(p1);
n.sign=0;
}
else
p=p->next;
}
}
void in_closed(node n)//將n節世亂點放入closed表
{
while(q->next!=closed)
{
if(n.f>=q->fnode.f)
{
q->next->pri=(link *)malloc(sizeof(link));
q->next->pri->pri=q;
q=q->next;
q->pri->next=p;
q->pri->pri->next=q->pri;
q=q->pri;
q->fnode.flag=n.flag;
q->fnode.f=n.f;
q->fnode.g=n.g;
q->fnode.h=n.h;
q->fnode.x=n.x;
q->fnode.y=n.y;
q->fnode.old=n.old;
q->fnode.sign=n.sign=2;
}
else
q=q->next;
}
closed->pri=(link *)malloc(sizeof(link));
closed->pri->pri=q;
closed->pri->next=closed;
q->next=closed->pri;
q=q->next;
q->fnode.flag=n.flag;
q->fnode.f=n.f;
q->fnode.g=n.g;
q->fnode.h=n.h;
q->fnode.x=n.x;
q->fnode.y=n.y;
q->fnode.old=n.old;
q->fnode.sign=n.sign=2;
}
void out_closed(node n)//將n節點從closed表中移出
{
q=closed;
while(q->next!=closed)
{
if(n.f=q->fnode.f)
{
link *q1;
q1=q->next;
q->next=q->next->next;
q->next->pri=q;
free(q1);
n.sign=0;
}
else
q=q->next;
}
}
void in_bestnode(node n)//將n節點設為bestnode節點
{
while(r->next!=bestnode)
{
if(n.f>=r->fnode.f)
{
r->next->pri=(link *)malloc(sizeof(link));
r->next->pri->pri=r;
r=r->next;
r->pri->next=r;
r->pri->pri->next=r->pri;
r=r->pri;
r->fnode.flag=n.flag;
r->fnode.f=n.f;
r->fnode.g=n.g;
r->fnode.h=n.h;
r->fnode.x=n.x;
r->fnode.y=n.y;
r->fnode.old=n.old;
}
else
r=r->next;
}
bestnode->pri=(link *)malloc(sizeof(link));
bestnode->pri->pri=r;
bestnode->pri->next=bestnode;
r->next=bestnode->pri;
r=r->next;
r->fnode.flag=n.flag;
r->fnode.f=n.f;
r->fnode.g=n.g;
r->fnode.h=n.h;
r->fnode.x=n.x;
r->fnode.y=n.y;
r->fnode.old=n.old;
}
void out_bestnode(node n)//將n節點的bestnode去掉
{
r=bestnode;
while(r->next!=bestnode)
{
if(n.f=p->fnode.f)
{
link *r1;
r1=r->next;
r->next=r->next->next;
r->next->pri=r;
free(r1);
}
else
r=r->next;
}
}
void in_successor(node n)//將n節點設置為successor節點
{
s=successor;
while(s->next!=successor)
{
if(n.f>=s->fnode.f)
{
s->next->pri=(link *)malloc(sizeof(link));
s->next->pri->pri=s;
s=p->next;
s->pri->next=s;
s->pri->pri->next=s->pri;
s=s->pri;
s->fnode.flag=n.flag;
s->fnode.f=n.f;
s->fnode.g=n.g;
s->fnode.h=n.h;
s->fnode.x=n.x;
s->fnode.y=n.y;
s->fnode.old=n.old;
}
else
s=s->next;
}
successor->pri=(link *)malloc(sizeof(link));
successor->pri->pri=s;
successor->pri->next=successor;
s->next=successor->pri;
s=s->next;
s->fnode.flag=n.flag;
s->fnode.f=n.f;
s->fnode.g=n.g;
s->fnode.h=n.h;
s->fnode.x=n.x;
s->fnode.y=n.y;
s->fnode.old=n.old;
}
void out_successor(node n)//將n節點的successor去掉
{
s=successor;
while(s->next!=successor)
{
if(n.f=p->fnode.f)
{
link *s1;
s1=s->next;
s->next=s->next->next;
s->next->pri=s;
free(s1);
}
else
s=s->next;
}
}
void print(link *n)//輸出link類型的表n
{
link *forprint;
forprint=n;
printf("the key is ");
while(forprint->next!=n)
printf("(%d,%d)\n",forprint->fnode.x,forprint->fnode.y);
}
int main()
{
//初始化部分
//這部分的功能是將二維的整形數組賦值給node型的二維數組
int i=0,j=0;
for(i=0;i<7;i++)
for(j=0;j<7;j++)
{
maze[i][j].x=i;
maze[i][j].y=j;
maze[i][j].flag=maze_flag[i][j];
if(maze[i][j].flag==0)
{
maze[i][j].h=6-i+6-j;
maze[i][j].sign=maze[i][j].f=maze[i][j].g=maze[i][j].old=0;
}
else
maze[i][j].h=-1;
}
for(i=0;i<7;i++)//輸出迷宮示意圖
{
for(j=0;j<7;j++)
{
printf("%2d",maze_flag[i][j]);
}
printf("\n");
}
//這部分的功能是將open,closed,bestnode表初始化,都置為空表
p=open=(link *)malloc(sizeof(link));
open->next=open;
open->pri=open;
q=closed=(link *)malloc(sizeof(link));
closed->next=closed;
closed->pri=closed;
r=bestnode=(link *)malloc(sizeof(link));
bestnode->next=bestnode;
bestnode->pri=bestnode;
//將第一個元素即(0,0)節點放入open表,開始演算法
in_open(maze[0][0]);
maze[0][0].f=maze[0][0].h;
link *s2;
s2=successor;
if(open->next!=open)//open表為空時則失敗退出
{
while(1)
{
in_bestnode(open->fnode);//將open表的第一個元素放入bestnode中
in_closed(maze[open->fnode.x][open->fnode.y]);//將open表的第一個元素放入closed中
maze[open->fnode.x][open->fnode.y].g++;//將open表的第一個元素的g值加一,表示已經走了一步
out_open(maze[open->fnode.x][open->fnode.y]);//將open表的第一個元素刪除
if(bestnode->fnode.x==6&&bestnode->fnode.y==6)//若bestnode是目標節點,則成功退出
{
printf("succes!!\nthen print the key:\n");
print(closed);
break;
}
else//若bestnode不是目標節點,則擴展其臨近可以走的節點為successor
{
if(i==0||j==0||i==6||j==6)
{
if(i==0&&j==0)//若為(0,0),則判斷右邊和下邊的元素
{
if(judge(maze[i][j+1])==0)
in_successor(maze[i][j+1]);
if(judge(maze[i+1][j])==0)
in_successor(maze[i+1][j]);
}
else if(i==0&&j==6)//若為(0,6),則判斷左邊和下邊的元素
{
if(judge(maze[i-1][j])==0)
in_successor(maze[i-1][j]);
if(judge(maze[i+1][j])==0)
in_successor(maze[i+1][j]);
}
else if(i==6&&j==0)//若為(6,0),則判斷左邊和上邊的元素
{
if(judge(maze[i-1][j])==0)
in_successor(maze[i-1][j]);
if(judge(maze[i][j-1])==0)
in_successor(maze[i][j-1]);
}
else if(i==6&&j==6)//若為(6,6),則判斷左邊和上邊的元素
{
if(judge(maze[i-1][j])==0)
in_successor(maze[i-1][j]);
if(judge(maze[i][j-1])==0)
in_successor(maze[i][j-1]);
}
else if(i==0)//若為第一行的元素(不在角上),則判斷左邊,下邊和右邊
{
if(judge(maze[i][j+1])==0)
in_successor(maze[i][j+1]);
if(judge(maze[i][j-1])==0)
in_successor(maze[i][j-1]);
if(judge(maze[i+1][j])==0)
in_successor(maze[i+1][j]);
}
else if(i==6)//若為第七行的元素(不在角上),則判斷左邊,上邊和右邊
{
if(judge(maze[i][j+1])==0)
in_successor(maze[i][j+1]);
if(judge(maze[i][j-1])==0)
in_successor(maze[i][j-1]);
if(judge(maze[i-1][j])==0)
in_successor(maze[i-1][j]);
}
else if(j==0)//若為第一列的元素(不在角上),則判斷右邊,下邊和上邊
{
if(judge(maze[i+1][j])==0)
in_successor(maze[i+1][j]);
if(judge(maze[i-1][j])==0)
in_successor(maze[i-1][j]);
if(judge(maze[i][j+1])==0)
in_successor(maze[i][j+1]);
}
else if(j==6)//若為第七列的元素(不在角上),則判斷左邊,上邊和上邊
{
if(judge(maze[i+1][j])==0)
in_successor(maze[i+1][j]);
if(judge(maze[i-1][j])==0)
in_successor(maze[i-1][j]);
if(judge(maze[i][j-1])==0)
in_successor(maze[i][j-1]);
}
}
else//若為中將的元素,則判斷四個方向的節點
{
if(judge(maze[i][j-1])==0)
in_successor(maze[i][j-1]);
if(judge(maze[i][j+1])==0)
in_successor(maze[i][j+1]);
if(judge(maze[i-1][j])==0)
in_successor(maze[i-1][j]);
if(judge(maze[i+1][j])==0)
in_successor(maze[i+1][j]);
}
}
while(s2->next!=successor)//對所有的successor節點進行下列操作
{
maze[s2->fnode.x][s2->fnode.y].g=bestnode->fnode.g+bestnode->fnode.h;//計算g(suc)=g(bes)+h(bes,suc)
if(s2->fnode.sign==1)//若在open表中,則置為old,記下較小的g,並從open表中移出,放入closed表中
{
s2->fnode.old=1;
if(s2->fnode.g<maze[s2->fnode.x][s2->fnode.y].g)
{
maze[s2->fnode.x][s2->fnode.y].g=s2->fnode.g;
maze[s2->fnode.x][s2->fnode.y].f=maze[s2->fnode.x][s2->fnode.y].g+maze[s2->fnode.x][s2->fnode.y].h;
out_open(maze[s2->fnode.x][s2->fnode.y]);
in_closed(maze[s2->fnode.x][s2->fnode.y]);
maze[s2->fnode.x][s2->fnode.y].old=0;
}
else
continue;
}
else if(s2->fnode.sign==2)//若在closed表中,則置為old,記下較小的g,並將old從closed表中移出,將較小的g的節點放入closed表中
{
s2->fnode.old=1;
if(s2->fnode.g<maze[s2->fnode.x][s2->fnode.y].g)
{
maze[s2->fnode.x][s2->fnode.y].g=s2->fnode.g;
maze[s2->fnode.x][s2->fnode.y].f=maze[s2->fnode.x][s2->fnode.y].g+maze[s2->fnode.x][s2->fnode.y].h;
out_closed(maze[s2->fnode.x][s2->fnode.y]);
in_closed(maze[s2->fnode.x][s2->fnode.y]);
maze[s2->fnode.x][s2->fnode.y].old=0;
}
else
continue;
}
else//若即不再open表中也不在closed表中,則將此節點放入open表中,並計算此節點的f值
{
in_open(maze[s2->fnode.x][s2->fnode.y]);
maze[s2->fnode.x][s2->fnode.y].f=maze[s2->fnode.x][s2->fnode.y].g+maze[s2->fnode.x][s2->fnode.y].h;
}
s2=s2->next;
}
s2=successor;
}
}
else
printf("error!!This maze does not have the answer!");
return(0);
}
H. 如何用C語言編寫一個迷宮程序
#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還是不錯滴
}
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; //迷宮行,列 [/M]
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("你建立的迷宮為(最外圈為強)...\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}};//行增量和列增量 方向依次為東西南北 [/M]
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");
}
I. 誠求用C語言編一個實現走迷宮問題的代碼。
全部程序分幾個文件，看清楚了，每段程序放入一個文件，每段程序前面都有文件名：
//stackoperation.cpp
Status InitStack(SqStack &S)
{ //構造一個空棧S
S.base = (SElemType *)malloc(RANGE*sizeof(SElemType));
if(!S.base) exit(OVERFLOW); //存儲分配失敗
S.top = S.base;
S.stacksize = RANGE;
return OK;
}//Initstack
Status Push(SqStack &S,SElemType e)
{ //插入元素e為新的棧頂元素
if(S.top - S.base >= S.stacksize){//棧滿，追加存儲空間
S.base = (SElemType*)realloc(S.base,(S.stacksize + STACKINCREMENT) * sizeof(SElemType));
if(!S.base) exit(OVERFLOW); //存儲分配失敗
S.top = S.base + S.stacksize;
S.stacksize += STACKINCREMENT;
}
*S.top++ = e;
return OK;
}//Push
Status Pop(SqStack &S,SElemType &e){
/*若棧不空，則刪除S的棧頂元素，用e返回其值，並返回OK；
否則返回ERROR*/
if(S.top == S.base) return ERROR;
e = * --S.top;
return OK;
}//Pop
bool StackEmpty(SqStack S)
{ //判斷棧是否為空並返回TURN或FALSE
if(S.top == S.base) return TURE;
return FALSE;
}//StackEmpty
void PrintStack()
{
SqStack ST;
SElemType e;
InitStack(ST);
do{
Pop(SqS,e);
Push(ST,e);
}while(!StackEmpty(SqS));
do{
Pop(ST,e);
printf("(%d,%d,%d)",e.seat.i,e.seat.j,e.di);
}while(!StackEmpty(ST));
}
//migong.cpp
#include "Basetype.h"
#include "stackoperation.cpp"
#include "Mazeoperation.cpp"
void main()
{
char filename[15];
FILE *fp;
printf("請輸入迷宮數據文件名（長度不超過15個字元）：");
scanf("%s",&filename);
//如找不到文件，則要求重新輸入（最多三次機會）
for(int i=0;i<3;i++){
if((fp = fopen(filename,"r")) == NULL)
{printf("不能打開文件,請重新輸入文件名（長度不超過15個字元）：\n");
scanf("%s",filename);
}//if
break;
}//for
//讀取迷宮的行數和列數
int rnum,cnum;
fscanf(fp,"%d,%d",&rnum,&cnum);
printf("這個迷宮有%d行，%d列\n",rnum,cnum);
if(rnum>RANGE-2 || cnum>RANGE-2)
{ printf("迷宮太大，無法求解\n");
return;
}//判斷迷宮的大小是否符合要求
//初始化一個迷宮變數
MazeType maze;
for(i=0;i<=rnum+1;i++)
for(int j=0;j<=cnum+1;j++)
maze.arr[i][j] = '#';
CreatMaze(maze,rnum,cnum,fp);//創建迷宮
fclose(fp);//關閉迷宮文件
//列印當前迷宮
printf("當前迷宮為：\n");
for(i=0;i<=rnum+1;i++)
{ for(int j=0;j<=cnum+1;j++)
printf("%c",maze.arr[i][j]);
printf("\n");
}
printf("其中'#'表示障礙,外圍一圈'#'為圍牆\n");
//讀取入口及出口位置
PosType startp,endp;
printf("請輸入入口位置（兩數中間以逗號相隔）：");
scanf("%d,%d",&startp.i,&startp.j);
printf("請輸入出口位置（兩數中間以逗號相隔）：");
scanf("%d,%d",&endp.i,&endp.j);
if(MazePath(maze,startp,endp))
{ PrintMaze(maze,rnum,cnum);//將求解的迷宮輸出到文件保存，並列印到屏幕
PrintStack();//如果存在路徑則列印之
}
else printf("此迷宮不存在路徑\n");
}//main
//Mazeoperation.cpp
bool Pass(MazeType maze,PosType curpos)
{ //判斷當前位置是否可通，並返回值
switch(char ch = maze.arr[curpos.i][curpos.j])
{ case' ': return(FALSE);
case'#':
case'@':
case'*': return(TURE);
default: { printf("迷宮中第%d行,第%d列出現不明字元%c\n",
curpos.i,curpos.j,ch);exit(0);}
}//switch
}//pass
void FootPrint(MazeType &maze,PosType curpos)
{
maze.arr[curpos.i][curpos.j] = '*';
}//FootPrint
void MarkPrint(MazeType &maze,PosType curpos)
{
maze.arr[curpos.i][curpos.j] = '@';
}//MarkPrint
void NextPos(PosType &curpos,int di)
{
switch(di)
{ case 1: curpos.j++;break;
case 2: curpos.i++;break;
case 3: curpos.j--;break;
case 4: curpos.i--;break;
default: printf("當前方向%d無效\n",di);
exit(0);
}//switch
}//NextPos
bool MazePath(MazeType &maze,PosType start,PosType end){
SElemType e;
InitStack(SqS);
PosType curpos = start;
int curstep = 1;
do{
if(!Pass(maze,curpos)){
FootPrint(maze,curpos);
e.order = curstep;
e.seat.i = curpos.i;e.seat.j = curpos.j;
e.di = 1;
Push(SqS,e);
if(curpos.i == end.i && curpos.j == end.j) return(TURE);
NextPos(curpos,1);
curstep++;
}//if
else{
if(!StackEmpty(SqS)){
Pop(SqS,e);
while(e.di == 4 && !StackEmpty(SqS)){
MarkPrint(maze,e.seat); Pop(SqS,e);
}//while
if(e.di<4){
e.di++; Push(SqS,e);
NextPos(e.seat,e.di);
curpos.i = e.seat.i;curpos.j = e.seat.j;
}//if
}//if
}//else
}while(!StackEmpty(SqS));
return(FALSE);
}//Mazepath
void CreatMaze(MazeType &maze,int row,int col,FILE *fp){
//建立迷宮
char ch = fgetc(fp);
for(int i=1;i<=row;i++)
{
for(int j=1;j<=col;j++)
{switch( ch = fgetc(fp))
{
case'0': maze.arr[i][j]=' ';break;
case'1': maze.arr[i][j]='#';break;
default: printf("迷宮第%d行第%d列數據為%c有錯誤",i,j,ch);exit(0);
}//switch
}//for
fseek(fp,2,1);
}//for
fclose(fp);
}//CreatMaze
void PrintMaze(MazeType maze,int row,int col)
{ //列印結果並輸出到文件保存
FILE *out;
if((out = fopen("outfile","w"))==NULL)
{ printf("不能打開文件\n");
exit(0);
}//if
for(int i=0;i<=row+1;i++)
{for(int j=0;j<=col+1;j++)
{ fputc(maze.arr[i][j],out);
printf("%c",maze.arr[i][j]);
}
printf("\n");
}
printf("其中'*'號代表路徑，'#'代表障礙,'@'代表死胡同\n");
fclose(out);//關閉文件
}
//Basetype.h
#include <stdio.h>
#include "stdlib.h"
#define RANGE 30 //棧的存儲空間初始分配量，
//以及用來存放迷宮的字元數組的最大維數
#define TURE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW -1
#define STACKINCREMENT 5 //棧的存儲空間分配增量
typedef struct{
int i; //行坐標
int j; //列坐標
}PosType; //迷宮中坐標位置類型
//棧的定義
typedef struct{
int order; //通道塊在路徑上的「方向」
PosType seat; //通道塊在迷宮中的「坐標位置」
int di; //從此通道塊走向下一通道塊的「方向」
}SElemType; //棧的元素類型
typedef struct{
SElemType *base; //棧底指針
SElemType *top; //棧頂指針
int stacksize; //當前已分配的存儲空間，以元素為單位
}SqStack;
//迷宮的定義
typedef struct{
int m,n;
char arr[RANGE][RANGE];
}MazeType;
typedef int Status;
SqStack SqS; //定義一個棧
J. 迷宮問題，C語言
#include<stdio.h>
int main(void)
{
int maze[100][100];
int MAZE[100][100];
int m,n;
int p,q;
printf("輸入迷宮的行數m,列隱氏數n:\n");
scanf("%d%d",&m,&n);
for(p=0;p<=n+1;p++){
maze[0][p]=1;
maze[m+1][p]=1;
}
for(p=1;p<=m;p++){
maze[p][0]=1;
maze[p][n+1]=1;
printf("寬做輸入第%d行迷宮:\n",p);
for(q=1;q<=n;q++){
scanf("%d",&maze[p][q]);
MAZE[p][q]=maze[p][q];
}
}
struct location{
int row;
int col;
}way[100];
int movehoriz[8]={-1,0,1,1,1,0,-1,-1};
int movevert[8]={1,1,1,0,-1,-1,-1,0};
int endrow=m;
int endcol=n;
way[0].row=1;
way[0].col=1;
int start=3;
int i=0;
int k;
int j;
int found=0;
while(!found){
for(k=start;k<start+8;k++){
if((maze[way[i].row+movevert[k%8]][way[i].col+movehoriz[k%8]]==0)&&((i==0)||((way[i].row!=way[i-1].row)||(way[i].col!=way[i-1].col)))){
way[i+1].row=way[i].row+movevert[k%8];
way[i+1].col=way[i].col+movehoriz[k%8];
i++;
start=(k+5)%8;
break;
}
if((way[i].row==endrow)&&(way[i].col==endcol)){
break;
}
if((maze[way[i].row+movevert[k]][way[i].col+movehoriz[k]]==0)&&(way[i].row==way[i-1].row)&&(way[i].col==way[i-1].col)){
way[i].row=0;
way[i].col=0;
maze[way[i].row][way[i].col]=1;
i--;
start=(start+4)%8;
}
}
if(k>=start+8){
break;
}
if((way[i].row==endrow)||(way[i].col==endcol)){
found=1;
break;
}
}
if(found){
for(j=0;j<=i;j++){
printf("maze[%d][%d]\n",way[j].row,way[j].col);
}
}
else{
printf("The maze does not have a path\n");
}
}
QQ：366597114 不一定完全對。也許有灶巧散小錯誤。有問題可以來問我哈