隨機迷宮演算法
『壹』 c++ 迷宮 如何使大小隨機
用戶輸入迷宮規模，行數m，列數n。
隨機生成一個m*n的迷宮。
如果滿足要求，輸出迷宮和可行路徑。
否則繼續隨機生成。
如果n和m比較大的話，程序跑的比較慢。
『貳』 數據結構：用什麼演算法可以走出迷宮
演算法應該很多的，循環的，遞歸的，還有用棧的我有兩個可以看看，第一個是網路上下的，後面的是我自己編的和修改的
1.
//////////////////////////////////////////////////////////////////////
//文件名 :Maze.cpp
//功能 : 線性表的應用——迷宮求解
//創建 : 2007.6.20
//修改日期 : 2007.6.20
//作者 :
////////////////////////////////////////////////////////////////////////
#include <windows.h>
#include <iostream>
#include <stdio.h>
#include<time.h>
//#include "format.h"
//#include "stack.h"
using namespace std;
#define OK 0
#define ERR -1
#define UP '↑' //用於存儲方向的常量
#define DOWN '↓'
#define LEFT '→'
#define RIGHT '←'
#define Rank 20
#define File 63
#define Rand 16
char Maze[Rank][File]; //定義存儲迷宮用的字元型二維數組
char mark=1; //標記
char Bar=2; //地圖
char Player=12; //游戲者
typedef struct SNode
{
int data;
struct SNode *next;
}SNode;
typedef struct
{
int length;
SNode *top;
}STACK;
void InitStack(STACK *S)
{
S->top=NULL;
S->length=0;
}
/*元素e入棧*/
int Push(STACK *S,int e)
{
SNode *p;
p=new SNode[sizeof(SNode)];
if(!p) return ERR;
p->data=e;
p->next=S->top;
S->top=p;
S->length++;
return OK;
}
/*棧頂元素出棧,e帶回棧頂元數*/
int Pop(STACK *S,int *e)
{
SNode *p;
if(S->top==NULL) return ERR;
p=S->top;
*e=p->data;
S->top=p->next;
S->length--;
delete p;
return OK;
}
/*判斷S是否為空棧*/
int Empty(STACK S)
{
if(S.top==NULL) return OK;
return ERR;
}
void ShowMaze();
void InitMaze();
void RunMaze();
int main()
{
int i=1;
system("color 1E");
while(i==1)
{
RunMaze();
cout<<"\t\t 『選擇：Prsss 1：再來一次 Else：退出程序』\n";
cin>>i;
}
return 0;
}
void ShowMaze()
{
int i,j;
system("cls");
cout<<"\n\t\t\t 『迷 宮 求 解』"<<"\n";
cout<<"\t\t 『注:"<<Player<<"為游戲者"<<Bar<<"為地圖障礙"<<mark<<"為所留印記』"<<endl;
for(i=0;i<Rank;i++)
{
cout<<"\t"<<Bar;
for(j=0;j<File;j++)
cout<<Maze[i][j];
cout<<Bar<<"\n";
}
}
void InitMaze()
{
int i,j;
for(i=0;i<Rank;i++)
for(j=0;j<File;j++)
Maze[i][j]=Bar;
srand((unsigned)time(NULL));
int n;
cout<<"請輸入數字選圖";
cin>>n;
for(i=1;i<Rank-1;i++) //for開始
for(j=1;j<File;j++)
{
//n=rand()%Rand; //隨機函數
//if(n<Rand*2/3) Maze[i][j]=' ';
if (((n^i+4*j^3))%11!=5)Maze[i][j]=' ';
} //for結束
Maze[1][0]=' '; //給迷宮留入口
Maze[1][1]=' ';
Maze[1][2]=' ';
Maze[1][3]=' ';
Maze[Rank-2][File-4]=' '; //給迷宮留出口
Maze[Rank-2][File-3]=' ';
Maze[Rank-2][File-2]=' ';
Maze[Rank-2][File-1]=' ';
}
void RunMaze()
{
int path,i=1,j=0,speed=0;
time_t Start,End;
STACK S; //定義一個用於存儲走過的路線的棧
time(&Start);
InitMaze(); //隨機成生迷宮
InitStack(&S); //初始化棧
Maze[1][0]=Player; //初始化位置
ShowMaze(); //顯示迷宮
cout<<"\n\t\t\t『請選擇速度:1 快速 2 較慢 』"<<endl;
while(speed!=1 && speed!=2) cin>>speed;
while(i>=0 && i<Rank && j>=0 && j<File)//開始遍歷迷宮
{
ShowMaze(); //顯示迷宮
if(speed==2) //選擇2較慢時進入空循環延時
Sleep(100);
if(i==Rank-2&&j==File-1) //判斷是否到達出口
{
time(&End);
cout<<"\n\t\t『恭喜成功走出!所用的步數為:"<<S.length<<" 所用時間："<<End-Start<<" 秒』"<<endl;
return;
}
if(Maze[i][j+1]==' ') //向右走一步
{
char dir=26;
Maze[i][j]=dir;
j=j+1;
Maze[i][j]=Player;
Push(&S,RIGHT);
}
else
{
if(Maze[i+1][j]==' ') //向下走一步
{
char dir=25;
Maze[i][j]=dir;
i=i+1;
Maze[i][j]=Player;
Push(&S,DOWN);
}
else
{
if(Maze[i-1][j]==' ') //向上走一步
{
char dir=24;
Maze[i][j]=dir;
i=i-1;
Maze[i][j]=Player;
Push(&S,UP);
}
else
{
if(Maze[i][j-1]==' ') //向左走一步
{
char dir=27;
Maze[i][j]=dir;
j=j-1;
Maze[i][j]=Player;
Push(&S,LEFT);
}
else //遇到障礙往回走一步
{
if(Empty(S)==OK) //判斷是否回到起點了,是則退出程序
{
time(&End);
cout<<"\n\t\t\t『迷宮沒有出路! 所用時間："<<End-Start<<"秒』\n";
return;
}
else
{
if(Pop(&S,&path)==OK) //判斷能否取回上一步路徑
{
switch(path)
{
case LEFT:
Maze[i][j]=mark;
j=j+1;
Maze[i][j]=Player;
break;
case UP:
Maze[i][j]=mark;
i=i+1;
Maze[i][j]=Player;
break;
case DOWN:
Maze[i][j]=mark;
i=i-1;
Maze[i][j]=Player;
break;
case RIGHT:
Maze[i][j]=mark;
j=j-1;
Maze[i][j]=Player;
break;
} //結束分支語句switch
} //結束判斷能否取回上一步路徑
}
}
}
}
}
} //結束while循環
}
第二個。
#include <windows.h>
#include <iostream>
#include <stdio.h>
#include<time.h>
//#include "format.h"
//#include "stack.h"
using namespace std;
//#define OK 0
//#define ERR -1
//#define UP '↑' //用於存儲方向的常量
//#define DOWN '↓'
//#define LEFT '→'
//#define RIGHT '←'
#define Rank 17
#define File 63
#define Rand 16
char Maze[Rank][File]; //定義存儲迷宮用的字元型二維數組
char mark=1; //標記
char Bar=2; //地圖
char Player=12; //游戲者
void ShowMaze();
void InitMaze();
void RunMaze();
int main()
{
int i=1;
system("color 1E");
while(i==1)
{
RunMaze();
cout<<"\t\t 『選擇：Prsss 1：再來一次 Else：退出程序』\n";
cin>>i;
}
return 0;
}
void ShowMaze()
{
int i,j;
system("cls");
cout<<"\n\t\t\t 『迷 宮 求 解』"<<"\n";
cout<<"\t\t 『注:"<<Player<<"為游戲者"<<Bar<<"為地圖障礙"<<mark<<"為所留印記』"<<endl;
for(i=0;i<Rank;i++)
{
cout<<"\t"<<Bar;
for(j=0;j<File;j++)
cout<<Maze[i][j];
cout<<Bar<<"\n";
}
}
void InitMaze()
{
int i,j;
for(i=0;i<Rank;i++)
for(j=0;j<File;j++)
Maze[i][j]=Bar;
srand((unsigned)time(NULL));
int n=5;
cout<<"請輸入數字選圖";
cin>>n;
for(i=1;i<Rank-1;i++) //for開始
for(j=1;j<File;j++)
{
//n=rand()%Rand; //隨機函數
//if(n<Rand*2/3) Maze[i][j]=' ';
if (((n^i+4*j^3))%5!=1)Maze[i][j]=' ';
} //for結束
Maze[1][0]=' '; //給迷宮留入口
Maze[1][1]=' ';
Maze[1][2]=' ';
Maze[1][3]=' ';
Maze[Rank-2][File-4]=' '; //給迷宮留出口
Maze[Rank-2][File-3]=' ';
Maze[Rank-2][File-2]=' ';
Maze[Rank-2][File-1]=' ';
}
void RunMaze()
{ int a=2;
int i=1,j=1,speed=0;
time_t Start,End;
//STACK S; //定義一個用於存儲走過的路線的棧
time(&Start);
InitMaze(); //隨機成生迷宮
//InitStack(&S); //初始化棧
//Maze[1][0]=Player; //初始化位置
ShowMaze(); //顯示迷宮
cout<<"\n\t\t\t『請選擇速度:1 快速 2 較慢 』"<<endl;
while(speed!=1 && speed!=2) cin>>speed;
while(i>=0 && i<Rank && j>=0 && j<File)//開始遍歷迷宮
{
ShowMaze(); //顯示迷宮
if(speed==2) //選擇2較慢時進入空循環延時
Sleep(100);
if(i==Rank-2&&j==File-1) //判斷是否到達出口
{
time(&End);
cout<<"\n\t\t『恭喜成功走出!"<<" 所用時間："<<End-Start<<" 秒』"<<endl;
return ;
}
else
{
switch(a)
{
case 1:if (Maze[i-1][j]==' '||Maze[i-1][j]==26)
{i=i-1;
a=-2;
Maze[i][j]=26;
break;
}
else
if (Maze[i][j+1]==' '||Maze[i][j+1]==26)
{j=j+1;
a=1;
Maze[i][j]=26;
break;
}else
if (Maze[i+1][j]==' '||Maze[i+1][j]==26)
//if(Maze[i+1]][j]==' '||Maze[i+1][j]==26)
{i=i+1;
a=2;
Maze[i][j]=26;
break;
}
else
{
Maze[i][j]=26;
a=-a;
break;
}
case 2:if(Maze[i][j+1]==' '||Maze[i][j+1]==26)
{
j=j+1;
a=1;
Maze[i][j]=26;
break;
}
else
if(Maze[i+1][j]==' '||Maze[i+1][j]==26)
{
i=i+1;
a=2;
Maze[i][j]=26;
break;
}
else
if(Maze[i][j-1]==' '||Maze[i][j-1]==26)
{
j=j-1;
a=-1;
Maze[i][j]=26;
break;
}
else
{
Maze[i][j]=26;
a=-a;
break;
}
case -1:if (Maze[i+1][j]==' '||Maze[i+1][j]==26)
{i=i+1;
a=2;
Maze[i][j]=26;
break;
}
else
if (Maze[i][j-1]==' '||Maze[i][j-1]==26)
{j=j-1;
a=-1;
Maze[i][j]=26;
break;
}
else
if (Maze[i-1][j]==' '||Maze[i-1][j]==26)
{i=i-1;
a=-2;
Maze[i][j]=26;
break;
}
else
{
a=-a;
Maze[i][j]=26;
break;
}
case -2:if (Maze[i][j-1]==' '||Maze[i][j-1]==26)
{j=j-1;
a=-1;
Maze[i][j]=26;
break;
}
else
if (Maze[i-1][j]==' '||Maze[i-1][j]==26)
{i=i-1;
a=-2;
Maze[i][j]=26;
break;
}
else
if (Maze[i][j+1]==' '||Maze[i][j+1]==26)
{j=j+1;
a=1;
Maze[i][j]=26;
break;
}
else
{
Maze[i][j]=26;
a=-a;
break;
}
}
if (i==1&&j==1)
{
time(&End);
cout<<"迷宮沒有出路"<<"所用時間"<<End-Start<<endl;
return;
}
}
} //結束while循環
}
『叄』 數據結構與演算法作業：用c語言編程隨機生成一個迷宮，然後找出從入口到出口的路線圖。急！
幾點說明：
1．本程序是動態的，運行後自動尋找迷宮出路
2.本程序對C語言剛學完的有很大的意義．
3.四周是牆,坐標(1,1)是入口,右下腳是出口
聲明:本程序用VC調試是無法通過的需要修改
本程序調試工具是TC.....................
#include "graphics.h"
#include "dos.h"
#include "stdlib.h"
#include "process.h"
#define MAX_COL 14/*定義迷宮大小*/
#define MAX_ROW 14
typedef struct
{ int vert;
int horiz;
}offsets;
mapture(int i,int j,int k);/*標記迷宮，（i,j）標記為k模式*/
initmaze();/*初始化迷宮數組*/
findmaze(int i,int j);/*找到了（i,j）可走，標記*/
mapmaze();/*畫出原始迷宮*/
int findpath(int row,int col);/*遞歸函數，找出迷宮路徑*/
mapbar();/*畫出方格*/
initgrap();/*初始化VGA*/
print();/*迷宮走完後，輸出是否成功 */
int startx=50,starty=50;/*畫圖的屏幕坐標*/
int maze[MAX_ROW][MAX_COL];
offsets move[8]={{0,1},{1,1},{-1,1},{1,0},{-1,0},{0,-1},{1,-1},{-1,-1}}; /*8個方向尋找*/
initmaze()/*初始化迷宮數組 */
{ int i,j;
for(i=0;i<MAX_ROW;i++)/*迷宮四周設置為1 代表牆*/
{ maze[i][0]=1;
maze[i][MAX_COL-1]=1;
}
for(i=0;i<MAX_COL;i++)
{ maze[0][i]=1;
maze[MAX_ROW-1][i]=1;
}
randomize();
for(i=1;i<MAX_ROW-1;i++)/*迷宮圖形隨機產生 1表示不通 0表示可行*/
for(j=1;j<MAX_COL-1;j++)
{
maze[i][j]=random(2);
}
}
findmaze(int i,int j)/*找到 （i,j）可走*/
{
mapture(j,i,2);/*在圖形上標記*/
sleep(1);
}
returnmaze(int i,int j)/*找到（i,j）可走 ，但下一步無路走則標記*/
{
mapture(j,i,3);/*在圖形上標記*/
sleep(1);
}
print(int i)/*迷宮走完後，輸出是否成功*/
{ settextstyle(1,0,5);
if(i==1)
outtextxy(340,400,"Ture path!");
else if(i==2)
outtextxy(340,400,"No path!");
}
int findpath(int row,int col)/*用遞歸法找迷宮*/
{ int direct,next_row,next_col;
direct=0;
maze[1][1]=2;
mapture(1,1,2);
sleep(1);
while(direct<8)/*8個方向尋找*/
{ next_row=row+move[direct].vert;/*設置下一步坐標*/
next_col=col+move[direct].horiz;
if(maze[next_row][next_col]==0) /*可走，便標記*/
{ maze[next_row][next_col]=2;
findmaze(next_row,next_col) ;
if(next_row==(MAX_ROW-2)&&next_col==(MAX_COL-2))/*找到出口退出程序*/
{ print(1);
getch();
exit(0);
}
else
findpath(next_row,next_col);/*沒有到出口繼續遞歸*/
maze[next_row][next_col]=3;
returnmaze(next_row,next_col);
}
direct++;
}
return(row);
}
TC調試良好
『肆』 如何用c語言編寫迷宮游戲
#include <graphics.h>
#include <stdlib.h>
#include <stdio.h>
#include <conio.h>
#include <dos.h>
#define N 20/*
迷宮的大小，可改變
*/
int oldmap[N][N];/*
遞歸用的數組
,
用全局變數節約時間
*/
int yes=0;/*yes
是判斷是否找到路的標志
,1
找到，
0
沒找到
*/
int way[100][2],wayn=0;/*way
數組是顯示路線用的
,wayn
是統計走了幾個格
子
*/
void Init(void);/*
圖形初始化
*/
void Close(void);/*
圖形關閉
*/
void DrawPeople(int *x,int *y,int n);/*
畫人工探索物圖
*/
void PeopleFind(int (*x)[N]);/*
人工探索
*/
void
WayCopy(int
(*x)[N],int
(*y)[N]);/*
為了
8
個方向的遞歸，把舊迷宮圖
拷貝給新數組
*/
int FindWay(int (*x)[N],int i,int j);/*
自動探索函數
*/
void MapRand(int (*x)[N]);/*
隨機生成迷宮函數
*/
void PrMap(int (*x)[N]);/*
輸出迷宮圖函數
*/
void Result(void);/*
輸出結果處理
*/
void Find(void);/*
成功處理
*/
void NotFind(void);/*
失敗處理
*/
void main(void)/*
主函數
*/
{
int map[N][N]; /*
迷宮數組
*/
char ch;
clrscr();
printf("\n Please select hand(1) else auto\n");/*
選擇探索方式
*/
scanf("%c",&ch);
Init(); /*
初始化
*/
MapRand(map);/*
生成迷宮
*/
PrMap(map);/*
顯示迷宮圖
*/
if(ch=='1')
PeopleFind(map);/*
人工探索
*/
else
FindWay(map,1,1);/*
系統自動從下標
1,1
的地方開始探索
*/
Result();/*
輸出結果
*/
Close();
}
void Init(void)/*
圖形初始化
*/
{
int gd=DETECT,gm;
initgraph(&gd,&gm,"c:\\tc"); }
void DrawPeople(int *x,int *y,int n)/*畫人工控制圖*/ {/*如果將以下兩句注釋掉，則顯示人工走過的路徑，*/
setfillstyle(SOLID_FILL,WHITE); /*設置白色實體填充樣式*/ bar(100+(*y)*15-6,50+(*x)*15-6,100+(*y)*15+6,50+(*x)*15+6); /*恢復原通路*/
switch(n)/*判斷x,y的變化，8個方向的變化*/ {
case 1: (*x)--;break; /*上*/
case 2: (*x)--;(*y)++;break /*右上*/ case 3: (*y)++;break; /*右*/
case 4: (*x)++;(*y)++;break; /*右下*/ case 5: (*x)++;break; /*下*/
case 6: (*x)++;(*y)--;break; /*左下*/ case 7: (*y)--;break; /*左*/
case 8: (*x)--;(*y)--;break; /*左上*/ }
setfillstyle(SOLID_FILL,RED);/*新位置顯示探索物*/
bar(100+(*y)*15-6,50+(*x)*15-6,100+(*y)*15+6,50+(*x)*15+6); }
void PeopleFind(int (*map)[N])/*人工手動查找*/ {
int x,y;
char c=0;/*接收按鍵的變數*/ x=y=1;/*人工查找的初始位置*/ setcolor(11);
line(500,200,550,200); outtextxy(570,197,"d"); line(500,200,450,200); outtextxy(430,197,"a"); line(500,200,500,150); outtextxy(497,130,"w"); line(500,200,500,250); outtextxy(497,270,"x"); line(500,200,450,150); outtextxy(445,130,"q"); line(500,200,550,150); outtextxy(550,130,"e"); line(500,200,450,250); outtextxy(445,270,"z"); line(500,200,550,250);
outtextxy(550,270,"c");/*以上是畫8個方向的控制介紹*/
setcolor(YELLOW);
outtextxy(420,290,"Press 'Enter' to end");/*壓回車鍵結束*/ setfillstyle(SOLID_FILL,RED);
bar(100+y*15-6,50+x*15-6,100+y*15+6,50+x*15+6);/*入口位置顯示*/ while(c!=13)/*如果按下的不是回車鍵*/ {
c=getch();/*接收字元後開始各個方向的探索*/ if(c=='w'&&map[x-1][y]!=1) DrawPeople(&x,&y,1);/*上*/ else if(c=='e'&&map[x-1][y+1]!=1) DrawPeople(&x,&y,2);/*右上*/ else if(c=='d'&&map[x][y+1]!=1) DrawPeople(&x,&y,3);/*右*/ else if(c=='c'&&map[x+1][y+1]!=1) DrawPeople(&x,&y,4);/*右下*/ else if(c=='x'&&map[x+1][y]!=1) DrawPeople(&x,&y,5);/*下*/ else if(c=='z'&&map[x+1][y-1]!=1) DrawPeople(&x,&y,6); /*左下*/ else if(c=='a'&&map[x][y-1]!=1) DrawPeople(&x,&y,7); /*左*/ else if(c=='q'&&map[x-1][y-1]!=1) DrawPeople(&x,&y,8); /*左上*/ }
setfillstyle(SOLID_FILL,WHITE); /*消去紅色探索物，恢復原迷宮圖*/ bar(100+y*15-6,50+x*15-6,100+y*15+6,50+x*15+6); if(x==N-2&&y==N-2)/*人工控制找成功的話*/ yes=1; /*如果成功標志為1*/ }
void WayCopy(int (*oldmap)[N],int (*map)[N])/*拷貝迷宮數組 */ {
int i,j;
for(i=0;i<N;i++) for(j=0;j<N;j++) oldmap[i][j]=map[i][j]; }
int FindWay(int (*map)[N],int i,int j)/*遞歸找路*/ {
if(i==N-2&&j==N-2)/*走到出口*/ {
yes=1;/*標志為1,表示成功*/ return; }
map[i][j]=1;/*走過的地方變為1*/ WayCopy(oldmap,map); /*拷貝迷宮圖*/
if(oldmap[i+1][j+1]==0&&!yes)/*判斷右下方是否可走*/ {
FindWay(oldmap,i+1,j+1); if(yes)/*如果到達出口了，再把值賦給顯示路線的way數組,也正是這個原因,所以具體路線是從最後開始保存*/ { way[wayn][0]=i; way[wayn++][1]=j; return; } }
WayCopy(oldmap,map);
if(oldmap[i+1][j]==0&&!yes)/*判斷下方是否可以走,如果標志yes已經是1也不用找下去了*/ {
FindWay(oldmap,i+1,j); if(yes) { way[wayn][0]=i; way[wayn++][1]=j; return; } }
WayCopy(oldmap,map);
if(oldmap[i][j+1]==0&&!yes)/*判斷右方是否可以走*/ {
FindWay(oldmap,i,j+1); if(yes) { way[wayn][0]=i; way[wayn++][1]=j; return; } }
WayCopy(oldmap,map);
if(oldmap[i-1][j]==0&&!yes)/*判斷上方是否可以走*/ {
FindWay(oldmap,i-1,j); if(yes) { way[wayn][0]=i; way[wayn++][1]=j; return; } }
WayCopy(oldmap,map);
if(oldmap[i-1][j+1]==0&&!yes)/*判斷右上方是否可以走*/ {
FindWay(oldmap,i-1,j+1); if(yes) { way[wayn][0]=i; way[wayn++][1]=j; return; } }
WayCopy(oldmap,map);
if(oldmap[i+1][j-1]==0&&!yes)/*判斷左下方是否可以走*/ {
FindWay(oldmap,i+1,j-1); if(yes) { way[wayn][0]=i; way[wayn++][1]=j; return; } }
WayCopy(oldmap,map);
if(oldmap[i][j-1]==0&&!yes)/*判斷左方是否可以走*/ {
FindWay(oldmap,i,j-1); if(yes) { way[wayn][0]=i; way[wayn++][1]=j; return; } }
WayCopy(oldmap,map);
if(oldmap[i-1][j-1]==0&&!yes)/*判斷左上方是否可以走*/ {
FindWay(oldmap,i-1,j-1); if(yes) { way[wayn][0]=i; way[wayn++][1]=j; return; } }
return; }
void MapRand(int (*map)[N])/*開始的隨機迷宮圖*/ {
int i,j;
cleardevice();/*清屏*/
randomize(); /*隨機數發生器*/ for(i=0;i<N;i++) {
for(j=0;j<N;j++) { if(i==0||i==N-1||j==0||j==N-1)/*最外面一圈為牆壁*/ map[i][j]=1; else if(i==1&&j==1||i==N-2&&j==N-2)/*出發點與終點表示為可走的*/ map[i][j]=0; else map[i][j]=random(2);/*其它的隨機生成0或1*/ } } }
void PrMap(int (*map)[N])/*輸出迷宮圖*/ {
int i,j;
for(i=0;i<N;i++) for(j=0;j<N;j++) if(map[i][j]==0) { setfillstyle(SOLID_FILL,WHITE);/*白色為可走的路*/ bar(100+j*15-6,50+i*15-6,100+j*15+6,50+i*15+6); } else { setfillstyle(SOLID_FILL,BLUE);/*藍色為牆壁*/ bar(100+j*15-6,50+i*15-6,100+j*15+6,50+i*15+6);
} }
void Find(void)/*找到通路*/ {
int i;
setfillstyle(SOLID_FILL,RED);/*紅色輸出走的具體路線*/ wayn--;
for(i=wayn;i>=0;i--) {
bar(100+way[i][1]*15-6,50+way[i][0]*15-6,100+ way[i][1]*15+6,50+way[i][0]*15+6); sleep(1);/*控制顯示時間*/ }
bar(100+(N-2)*15-6,50+(N-2)*15-6,100+ (N-2)*15+6,50+(N-2)*15+6); /*在目標點標紅色*/ setcolor(GREEN);
settextstyle(0,0,2);/*設置字體大小*/ outtextxy(130,400,"Find a way!"); }
void NotFind(void)/*沒找到通路*/ {
setcolor(GREEN);
settextstyle(0,0,2);/*設置字體大小*/ outtextxy(130,400,"Not find a way!"); }
void Result(void)/*結果處理*/ {
if(yes)/*如果找到*/ Find();
else/*沒找到路*/ NotFind(); getch(); }
void Close(void)/*圖形關閉*/ {
closegraph(); }
『伍』 c語言程序設計的迷宮
這個可行的
/*4.3.3源程序*/
#include
<graphics.h>
#include
<stdlib.h>
#include
<stdio.h>
#include
<conio.h>
#include
<dos.h>
#define
N
20/*迷宮的大小，可改變*/
int
oldmap[N][N];/*遞歸用的數組,用全局變數節約時間*/
int
yes=0;/*yes是判斷是否找到路的標志,1找到，0沒找到*/
int
way[100][2],wayn=0;/*way數組是顯示路線用的,wayn是統計走了幾個格子*/
void
Init(void);/*圖形初始化*/
void
Close(void);/*圖形關閉*/
void
DrawPeople(int
*x,int
*y,int
n);/*畫人工探索物圖*/
void
PeopleFind(int
(*x)[N]);/*人工探索*/
void
WayCopy(int
(*x)[N],int
(*y)[N]);/*為了8個方向的遞歸，把舊迷宮圖拷貝給新數組*/
int
FindWay(int
(*x)[N],int
i,int
j);/*自動探索函數*/
void
MapRand(int
(*x)[N]);/*隨機生成迷宮函數*/
void
PrMap(int
(*x)[N]);/*輸出迷宮圖函數*/
void
Result(void);/*輸出結果處理*/
void
Find(void);/*成功處理*/
void
NotFind(void);/*失敗處理*/
void
main(void)/*主函數*/
{
int
map[N][N];
/*迷宮數組*/
char
ch;
clrscr();
printf("\n
Please
select
hand(1)
else
auto\n");/*選擇探索方式*/
scanf("%c",&ch);
Init();
/*初始化*/
MapRand(map);/*生成迷宮*/
PrMap(map);/*顯示迷宮圖*/
if(ch=='1')
PeopleFind(map);/*人工探索*/
else
FindWay(map,1,1);/*系統自動從下標1,1的地方開始探索*/
Result();/*輸出結果*/
Close();
}
void
Init(void)/*圖形初始化*/
{
int
gd=DETECT,gm;
initgraph(&gd,&gm,"c:\\tc");
}
void
DrawPeople(int
*x,int
*y,int
n)/*畫人工控制圖*/
{/*如果將以下兩句注釋掉，則顯示人工走過的路徑，*/
setfillstyle(SOLID_FILL,WHITE);
/*設置白色實體填充樣式*/
bar(100+(*y)*15-6,50+(*x)*15-6,100+(*y)*15+6,50+(*x)*15+6);
/*恢復原通路*/
switch(n)/*判斷x,y的變化，8個方向的變化*/
{
case
1:
(*x)--;break;
/*上*/
case
2:
(*x)--;(*y)++;break
;/*右上*/
case
3:
(*y)++;break;
/*右*/
case
4:
(*x)++;(*y)++;break;
/*右下*/
case
5:
(*x)++;break;
/*下*/
case
6:
(*x)++;(*y)--;break;
/*左下*/
case
7:
(*y)--;break;
/*左*/
case
8:
(*x)--;(*y)--;break;
/*左上*/
}
setfillstyle(SOLID_FILL,RED);/*新位置顯示探索物*/
bar(100+(*y)*15-6,50+(*x)*15-6,100+(*y)*15+6,50+(*x)*15+6);
}
void
PeopleFind(int
(*map)[N])/*人工手動查找*/
{
int
x,y;
char
c=0;/*接收按鍵的變數*/
x=y=1;/*人工查找的初始位置*/
setcolor(11);
line(500,200,550,200);
outtextxy(570,197,"d");
line(500,200,450,200);
outtextxy(430,197,"a");
line(500,200,500,150);
outtextxy(497,130,"w");
line(500,200,500,250);
outtextxy(497,270,"x");
line(500,200,450,150);
outtextxy(445,130,"q");
line(500,200,550,150);
outtextxy(550,130,"e");
line(500,200,450,250);
outtextxy(445,270,"z");
line(500,200,550,250);
outtextxy(550,270,"c");/*以上是畫8個方向的控制介紹*/
setcolor(YELLOW);
outtextxy(420,290,"Press
'Enter'
to
end");/*壓回車鍵結束*/
setfillstyle(SOLID_FILL,RED);
bar(100+y*15-6,50+x*15-6,100+y*15+6,50+x*15+6);/*入口位置顯示*/
while(c!=13)/*如果按下的不是回車鍵*/
{
c=getch();/*接收字元後開始各個方向的探索*/
if(c=='w'&&map[x-1][y]!=1)
DrawPeople(&x,&y,1);/*上*/
else
if(c=='e'&&map[x-1][y+1]!=1)
DrawPeople(&x,&y,2);/*右上*/
else
if(c=='d'&&map[x][y+1]!=1)
DrawPeople(&x,&y,3);/*右*/
else
if(c=='c'&&map[x+1][y+1]!=1)
DrawPeople(&x,&y,4);/*右下*/
else
if(c=='x'&&map[x+1][y]!=1)
DrawPeople(&x,&y,5);/*下*/
else
if(c=='z'&&map[x+1][y-1]!=1)
DrawPeople(&x,&y,6);
/*左下*/
else
if(c=='a'&&map[x][y-1]!=1)
DrawPeople(&x,&y,7);
/*左*/
else
if(c=='q'&&map[x-1][y-1]!=1)
DrawPeople(&x,&y,8);
/*左上*/
}
setfillstyle(SOLID_FILL,WHITE);
/*消去紅色探索物，恢復原迷宮圖*/
bar(100+y*15-6,50+x*15-6,100+y*15+6,50+x*15+6);
if(x==N-2&&y==N-2)/*人工控制找成功的話*/
yes=1;
/*如果成功標志為1*/
}
void
WayCopy(int
(*oldmap)[N],int
(*map)[N])/*拷貝迷宮數組
*/
{
int
i,j;
for(i=0;i<N;i++)
for(j=0;j<N;j++)
oldmap[i][j]=map[i][j];
}
int
FindWay(int
(*map)[N],int
i,int
j)/*遞歸找路*/
{
if(i==N-2&&j==N-2)/*走到出口*/
{
yes=1;/*標志為1,表示成功*/
return;
}
map[i][j]=1;/*走過的地方變為1*/
WayCopy(oldmap,map);
/*拷貝迷宮圖*/
if(oldmap[i+1][j+1]==0&&!yes)/*判斷右下方是否可走*/
{
FindWay(oldmap,i+1,j+1);
if(yes)/*如果到達出口了，再把值賦給顯示路線的way數組,也正是這個原因,所以具體路線是從最後開始保存*/
{
way[wayn][0]=i;
way[wayn++][1]=j;
return;
}
}
WayCopy(oldmap,map);
if(oldmap[i+1][j]==0&&!yes)/*判斷下方是否可以走,如果標志yes已經是1也不用找下去了*/
{
FindWay(oldmap,i+1,j);
if(yes)
{
way[wayn][0]=i;
way[wayn++][1]=j;
return;
}
}
WayCopy(oldmap,map);
if(oldmap[i][j+1]==0&&!yes)/*判斷右方是否可以走*/
{
FindWay(oldmap,i,j+1);
if(yes)
{
way[wayn][0]=i;
way[wayn++][1]=j;
return;
}
}
WayCopy(oldmap,map);
if(oldmap[i-1][j]==0&&!yes)/*判斷上方是否可以走*/
{
FindWay(oldmap,i-1,j);
if(yes)
{
way[wayn][0]=i;
way[wayn++][1]=j;
return;
}
}
WayCopy(oldmap,map);
if(oldmap[i-1][j+1]==0&&!yes)/*判斷右上方是否可以走*/
{
FindWay(oldmap,i-1,j+1);
if(yes)
{
way[wayn][0]=i;
way[wayn++][1]=j;
return;
}
}
WayCopy(oldmap,map);
if(oldmap[i+1][j-1]==0&&!yes)/*判斷左下方是否可以走*/
{
FindWay(oldmap,i+1,j-1);
if(yes)
{
way[wayn][0]=i;
way[wayn++][1]=j;
return;
}
}
WayCopy(oldmap,map);
if(oldmap[i][j-1]==0&&!yes)/*判斷左方是否可以走*/
{
FindWay(oldmap,i,j-1);
if(yes)
{
way[wayn][0]=i;
way[wayn++][1]=j;
return;
}
}
WayCopy(oldmap,map);
if(oldmap[i-1][j-1]==0&&!yes)/*判斷左上方是否可以走*/
{
FindWay(oldmap,i-1,j-1);
if(yes)
{
way[wayn][0]=i;
way[wayn++][1]=j;
return;
}
}
return;
}
void
MapRand(int
(*map)[N])/*開始的隨機迷宮圖*/
{
int
i,j;
cleardevice();/*清屏*/
randomize();
/*隨機數發生器*/
for(i=0;i<N;i++)
{
for(j=0;j<N;j++)
{
if(i==0||i==N-1||j==0||j==N-1)/*最外面一圈為牆壁*/
map[i][j]=1;
else
if(i==1&&j==1||i==N-2&&j==N-2)/*出發點與終點表示為可走的*/
map[i][j]=0;
else
map[i][j]=random(2);/*其它的隨機生成0或1*/
}
}
}
void
PrMap(int
(*map)[N])/*輸出迷宮圖*/
{
int
i,j;
for(i=0;i<N;i++)
for(j=0;j<N;j++)
if(map[i][j]==0)
{
setfillstyle(SOLID_FILL,WHITE);/*白色為可走的路*/
bar(100+j*15-6,50+i*15-6,100+j*15+6,50+i*15+6);
}
else
{
setfillstyle(SOLID_FILL,BLUE);/*藍色為牆壁*/
bar(100+j*15-6,50+i*15-6,100+j*15+6,50+i*15+6);
}
}
void
Find(void)/*找到通路*/
{
int
i;
setfillstyle(SOLID_FILL,RED);/*紅色輸出走的具體路線*/
wayn--;
for(i=wayn;i>=0;i--)
{
bar(100+way[i][1]*15-6,50+way[i][0]*15-6,100+
way[i][1]*15+6,50+way[i][0]*15+6);
sleep(1);/*控制顯示時間*/
}
bar(100+(N-2)*15-6,50+(N-2)*15-6,100+
(N-2)*15+6,50+(N-2)*15+6);
/*在目標點標紅色*/
setcolor(GREEN);
settextstyle(0,0,2);/*設置字體大小*/
outtextxy(130,400,"Find
a
way!");
}
void
NotFind(void)/*沒找到通路*/
{
setcolor(GREEN);
settextstyle(0,0,2);/*設置字體大小*/
outtextxy(130,400,"Not
find
a
way!");
}
void
Result(void)/*結果處理*/
{
if(yes)/*如果找到*/
Find();
else/*沒找到路*/
NotFind();
getch();
}
void
Close(void)/*圖形關閉*/
{
closegraph();
}
『陸』 誰有C語言，生成隨機迷宮的代碼
#include<stdio.h>
#include<conio.h>
#include<windows.h>
#include<time.h>
#defineHeight31//迷宮的高度，必須為奇數
#defineWidth25//迷宮的寬度，必須為奇數
#defineWall1
#defineRoad0
#defineStart2
#defineEnd3
#defineEsc5
#defineUp1
#defineDown2
#defineLeft3
#defineRight4
intmap[Height+2][Width+2];
voidgotoxy(intx,inty)//移動坐標
{
COORDcoord;
coord.X=x;
coord.Y=y;
SetConsoleCursorPosition(GetStdHandle(STD_OUTPUT_HANDLE),coord);
}
voidhidden()//隱藏游標
{
HANDLEhOut=GetStdHandle(STD_OUTPUT_HANDLE);
CONSOLE_CURSOR_INFOcci;
GetConsoleCursorInfo(hOut,&cci);
cci.bVisible=0;//賦1為顯示，賦0為隱藏
SetConsoleCursorInfo(hOut,&cci);
}
voidcreate(intx,inty)//隨機生成迷宮
{
intc[4][2]={0,1,1,0,0,-1,-1,0};//四個方向
inti,j,t;
//將方向打亂
for(i=0;i<4;i++)
{
j=rand()%4;
t=c[i][0];c[i][0]=c[j][0];c[j][0]=t;
t=c[i][1];c[i][1]=c[j][1];c[j][1]=t;
}
map[x][y]=Road;
for(i=0;i<4;i++)
if(map[x+2*c[i][0]][y+2*c[i][1]]==Wall)
{
map[x+c[i][0]][y+c[i][1]]=Road;
create(x+2*c[i][0],y+2*c[i][1]);
}
}
intget_key()//接收按鍵
{
charc;
while(c=getch())
{
if(c==27)returnEsc;//Esc
if(c!=-32)continue;
c=getch();
if(c==72)returnUp;//上
if(c==80)returnDown;//下
if(c==75)returnLeft;//左
if(c==77)returnRight;//右
}
return0;
}
voidpaint(intx,inty)//畫迷宮
{
gotoxy(2*y-2,x-1);
switch(map[x][y])
{
caseStart:
printf("入");break;//畫入口
caseEnd:
printf("出");break;//畫出口
caseWall:
printf("※");break;//畫牆
caseRoad:
printf("");break;//畫路
}
}
voidgame()
{
intx=2,y=1;//玩家當前位置，剛開始在入口處
intc;//用來接收按鍵
while(1)
{
gotoxy(2*y-2,x-1);
printf("☆");//畫出玩家當前位置
if(map[x][y]==End)//判斷是否到達出口
{
gotoxy(30,24);
printf("到達終點，按任意鍵結束");
getch();
break;
}
c=get_key();
if(c==Esc)
{
gotoxy(0,24);
break;
}
switch(c)
{
caseUp://向上走
if(map[x-1][y]!=Wall)
{
paint(x,y);
x--;
}
break;
caseDown://向下走
if(map[x+1][y]!=Wall)
{
paint(x,y);
x++;
}
break;
caseLeft://向左走
if(map[x][y-1]!=Wall)
{
paint(x,y);
y--;
}
break;
caseRight://向右走
if(map[x][y+1]!=Wall)
{
paint(x,y);
y++;
}
break;
}
}
}
intmain()
{
inti,j;
srand((unsigned)time(NULL));//初始化隨即種子
hidden();//隱藏游標
for(i=0;i<=Height+1;i++)
for(j=0;j<=Width+1;j++)
if(i==0||i==Height+1||j==0||j==Width+1)//初始化迷宮
map[i][j]=Road;
elsemap[i][j]=Wall;
create(2*(rand()%(Height/2)+1),2*(rand()%(Width/2)+1));//從隨機一個點開始生成迷宮，該點行列都為偶數
for(i=0;i<=Height+1;i++)//邊界處理
{
map[i][0]=Wall;
map[i][Width+1]=Wall;
}
for(j=0;j<=Width+1;j++)//邊界處理
{
map[0][j]=Wall;
map[Height+1][j]=Wall;
}
map[2][1]=Start;//給定入口
map[Height-1][Width]=End;//給定出口
for(i=1;i<=Height;i++)
for(j=1;j<=Width;j++)//畫出迷宮
paint(i,j);
game();//開始游戲
getch();
return0;
}
『柒』 怎樣生成隨機迷宮
首先，必須保證有一條可以通過的路。
大概思路：從數組的任一邊界開始將數組值設為0，然後利用隨機值設置隨機方向，如果方向上已有0，則繼續隨機，只到找到邊界為止。
生成可以通行的路之後，其它的就比較隨意了，看你喜歡怎麼處理了。
『捌』 在進行深度優先遍歷隨機創建迷宮時，怎麼尋找某一個單元格的鄰接單元格
變數 head 和 tail 是隊頭和隊尾指針， head 總是指向隊頭， tail 總是指向隊尾的下一個元素。每個點的 predecessor 成員也是一個指針，指向它的前趨在 queue 數組中的位置。如下圖所示：
廣度優先是一種步步為營的策略，每次都從各個方向探索一步，將前線推進一步，圖中的虛線就表示這個前線，隊列中的元素總是由前線的點組成的，可見正是隊列先進先出的性質使這個演算法具有了廣度優先的特點。廣度優先搜索還有一個特點是可以找到從起點到終點的最短路徑，而深度優先搜索找到的不一定是最短路徑。
#include <stdio.h>
#define MAX_ROW 5
#define MAX_COL 5
struct point { int row, col, predecessor; } queue[512];
int head = 0, tail = 0;
void enqueue(struct point p)
{
queue[tail++] = p;
}
struct point dequeue(void)
{
return queue[head++];
}
int is_empty(void)
{
return head == tail;
}
int maze[MAX_ROW][MAX_COL] = {
0, 1, 0, 0, 0,
0, 1, 0, 1, 0,
0, 0, 0, 0, 0,
0, 1, 1, 1, 0,
0, 0, 0, 1, 0,
};
void print_maze(void)
{
int i, j;
for (i = 0; i < MAX_ROW; i++) {
for (j = 0; j < MAX_COL; j++)
printf("%d ", maze[i][j]);
putchar('\n');
}
printf("*********\n");
}
void visit(int row, int col)
{
struct point visit_point = { row, col, head-1 };
maze[row][col] = 2;
enqueue(visit_point);
}
int main(void)
{
struct point p = { 0, 0, -1 };
maze[p.row][p.col] = 2;
enqueue(p);
while (!is_empty()) {
p = dequeue();
if (p.row == MAX_ROW - 1 /* goal */
&& p.col == MAX_COL - 1)
break;
if (p.col+1 < MAX_COL /* right */
&& maze[p.row][p.col+1] == 0)
visit(p.row, p.col+1);
if (p.row+1 < MAX_ROW /* down */
&& maze[p.row+1][p.col] == 0)
visit(p.row+1, p.col);
if (p.col-1 >= 0 /* left */
&& maze[p.row][p.col-1] == 0)
visit(p.row, p.col-1);
if (p.row-1 >= 0 /* up */
&& maze[p.row-1][p.col] == 0)
visit(p.row-1, p.col);
print_maze();
}
if (p.row == MAX_ROW - 1 && p.col == MAX_COL - 1)
{
printf("(%d, %d)\n", p.row, p.col);
while (p.predecessor != -1) {
p = queue[p.predecessor];
printf("(%d, %d)\n", p.row, p.col);
}
} else
printf("No path!\n");
return 0;
}
『玖』 隨機迷宮
#define OVERFLOW -2
#define ERROR 0
#define NULL 0
#define true 1
#define TRUE 1
#define false 0
#define FALSE 0
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
#include <stdio.h>
#include <stdlib.h>
/*
初始化迷宮,1表示通道,0表示牆
*/
int maze[8][8] = {
1,1,0,1,1,1,0,1,
1,1,0,1,1,1,0,1,
1,1,1,1,0,0,1,1,
1,0,0,0,1,1,1,1,
1,1,1,0,1,1,1,1,
1,0,1,1,1,0,1,1,
1,0,0,0,1,0,0,1,
0,1,1,1,1,1,1,1
};
//定義棧元素類型
typedef struct MStackElem
{
int x;//x坐標
int y;//y坐標
int val;//maze[x][y]的值
}MStackElem;
//定義棧
typedef struct {
MStackElem * base;
MStackElem * top;
int stackSize;
}MStack;
//=============Stack的實現========================
//初始化棧-------構造一個空棧
void initStack(MStack *s) {
s->base = (MStackElem *)malloc(STACK_INIT_SIZE * sizeof(MStackElem));
if (!s->base) {
printf("in initStack()...Failed to initalize the MStack ,no enough space! exit now. ");
exit(OVERFLOW);//存儲分配失敗
}
s->top = s->base;
s->stackSize = STACK_INIT_SIZE;
}
//向棧中添加元素
void push(MStack *s,MStackElem e) {
//向棧中添加元素前先判斷棧是否還有空間容納新元素
if (s->top - s->base >= s->stackSize) { //棧滿,追加元素
s->base = (MStackElem *)realloc(s->base, (STACK_INIT_SIZE+STACKINCREMENT) * sizeof(MStackElem));
if (!s->base) {
printf("in push()...Failed to realloc the MStack ,no enough space! exit now. ");
exit(OVERFLOW);//存儲分配失敗
}
s->top = s->base + s->stackSize; //因為是重新分配了空間,所以base的值其實已經改變,所以top的值也就相應的改變,才能指向新的迷宮棧
s->stackSize += STACKINCREMENT;
}
//將新元素加到棧頂
*(s->top++) = e;
}
//獲得棧頂元素
MStackElem getTop(MStack *s) {
if (s->top == s->base) {
printf("in getTop(),empty stack! exit now. ");
exit(ERROR);
}
else {
return *(s->top - 1);
}
}
//刪除棧頂元素
void pop(MStack *s) {
//若棧不為空,則刪除s的棧頂元素
if (s->top == s->base) {
printf("in pop(),empty stack! exit now. ");
exit(ERROR);
}
else {
--(s->top);
}
}
//=====================================求解迷宮的相關操作=====================//
//構造兩個棧,一個用來保存探索中的全部路徑,一個用來保存有效路徑
MStack realPath,path;
//判斷當前位置是否走過
int unPass(MStack path,MStackElem cur) {//這里不能傳path的地址,否則在遍歷過程中它的top值就真的被改了 !!
int flag = 1;
while(path.top != path.base)
{
MStackElem e = *(path.top - 1);
if (e.x == cur.x&& e.y == cur.y)
{
flag = 0;
}
//每循環一次令頭指針下移一個位置
(path.top)--;
}
return flag;
}
//獲得東面相鄰的位置
MStackElem getEast(MStackElem cur) {
if(cur.y != 7) {//當y==7時已到了迷宮右邊界,不能再向東(右)行了
cur.y += 1;
cur.val = maze[cur.x][cur.y];
}
return cur;// 當y==7時返回的是它本身
}
//獲得南面相鄰的位置
MStackElem getSouth(MStackElem cur) {
if(cur.x != 7) {//當x==7時已到了迷宮下邊界,不能再向南(下)行了
cur.x += 1;
cur.val = maze[cur.x][cur.y];
}
return cur;// 當x==7時返回的是它本身
}
//獲得西面相鄰的位置
MStackElem getWest(MStackElem cur) {
if(cur.y != 0) {//當y==0時已到了迷宮左邊界,不能再向西(左)行了
cur.y -= 1;
cur.val = maze[cur.x][cur.y];
}
return cur;// 當y==0時返回的是它本身
}
//獲得北面相鄰的位置
MStackElem getNorth(MStackElem cur) {
if(cur.x != 0) {//當cur.x==0時表示在迷宮的上邊界,不能再向北(上)行了
cur.x -= 1;
cur.val = maze[cur.x][cur.y];
}
return cur;// 當cur.x==0時返回的還是它本身
}
//獲得下一個可通行的位置,按東南西北的方向試探
MStackElem getNext(MStackElem cur) {
MStackElem next;
next.x = next.y=next.val = -1;
if(getEast(cur).val != 0 && unPass(path,getEast(cur))) {
next = getEast(cur);
}
else if(getSouth(cur).val != 0 && unPass(path,getSouth(cur))) {
next = getSouth(cur);
}
else if(getWest(cur).val != 0 && unPass(path,getWest(cur))) {
next = getWest(cur);
}
else if(getNorth(cur).val != 0 && unPass(path,getNorth(cur))) {
next = getNorth(cur);
}
//如果當前位置的四面或為牆或已走過,則返回的next的val值為-1
return next;
}
int getMazePath(){//獲得迷宮路徑的函數
MStackElem start,end,cur;
start.x = 0;
start.y = 0;
start.val = maze[start.x][start.y];
end.x = 7;
end.y = 7;
end.val = maze[end.x][end.y];
cur = start; //設定當前為位置為"入口位置"
//沒有重載=運算符,可以這樣用嗎,結果對嗎?試試吧:
/*
printf("%d",cur.x);
printf("%d",cur.y);
printf("%d",cur.val);
*/
//恩,結果是正確的,即可以通過cur=start來把start的值賦給cur.
//對了,想起來了,記得以前在學C++的復制構造函數時書上好像說過, 用=(等號)復制類對象時系統會調用由系統提供的復制的構造函數什麼的,
//唉,記不清了,還是基礎不扎實啊,以後可不能輕視基礎了@_@ ...
do
{
if (unPass(path,cur)) {//如果當前位置未曾走到過
push(&realPath,cur);
push(&path,cur);
cur = getNext(cur);
if (cur.x == end.x && cur.y == end.y) { //到達出口了,則跳出循環,並返回true
//把出口結點放入路徑中
push(&realPath,cur);
push(&path,cur);
//直接跳出函數(而不只是跳出這個循環 )
return true;
}
else if(cur.val == -1) {//當前位置的四面或為牆或已走過
//刪除真實路徑的棧頂元素
pop(&realPath);
cur = getTop(&realPath);//令cur指向棧頂元素
}
}
else {//如果當前位置已經走過,說明原來測試的方向不對,現在嘗試其它方向
cur = getNext(cur);
if (cur.val == -1) {//仍不通,刪除真實路徑的棧頂元素
pop(&realPath);
cur = getTop(&realPath);//令cur指向棧頂元素
}
}
} while (cur.x != end.x || cur.y != end.y);
}
//列印迷宮路徑
void printMazePath(MStack *s) {//為了安全,這里不傳MStack的地址,以防在遍歷的過程中把它們的top或base的值也修改了
/*注:這種方法實際是倒序列印出路徑,讓人看著別扭,所以我用下面的方法"倒序遍歷這個棧 '
while (s->top != s->base) {
MStackElem e = *(s->top-1);
printf("maze[%d][%d]----->",e.x,e.y);
(s->top)--;
}
*/
MStackElem e;
while (s->base < (s->top-1)) {
e = *(s->base);//先指向棧底元素,以後依次向上增1
printf("maze[%d][%d]----->",e.x,e.y);
(s->base)++;
}
//最後一個結點沒有後繼,所以不再輸出"------>"
e = *(s->base);
printf("maze[%d][%d]",e.x,e.y);
}
main(){
//初始化棧
initStack(&realPath);
initStack(&path);
getMazePath();
printf("The path of through the maze is:\n\n");
printMazePath(&realPath);
getchar();
}
『拾』 用數據結構解迷宮
#include <graphics.h>
#include <stdlib.h>
#include <stdio.h>
#include <conio.h>
#include <dos.h>
#define N 20/*迷宮的大小，可改變*/
int oldmap[N][N];/*遞歸用的數組,用全局變數節約時間*/
int yes=0;/*yes是判斷是否找到路的標志,1找到，0沒找到*/
int way[100][2],wayn=0;/*way數組是顯示路線用的,wayn是統計走了幾個格子*/
void Init(void);/*圖形初始化*/
void Close(void);/*圖形關閉*/
void DrawPeople(int *x,int *y,int n);/*畫人工探索物圖*/
void PeopleFind(int (*x)[N]);/*人工探索*/
void WayCopy(int (*x)[N],int (*y)[N]);/*為了8個方向的遞歸，把舊迷宮圖拷貝給新數組*/
int FindWay(int (*x)[N],int i,int j);/*自動探索函數*/
void MapRand(int (*x)[N]);/*隨機生成迷宮函數*/
void PrMap(int (*x)[N]);/*輸出迷宮圖函數*/
void Result(void);/*輸出結果處理*/
void Find(void);/*成功處理*/
void NotFind(void);/*失敗處理*/
void main(void)/*主函數*/
{
int map[N][N]; /*迷宮數組*/
char ch;
clrscr();
printf("\n Please select hand(1) else auto\n");/*選擇探索方式*/
scanf("%c",&ch);
Init(); /*初始化*/
MapRand(map);/*生成迷宮*/
PrMap(map);/*顯示迷宮圖*/
if(ch=='1')
PeopleFind(map);/*人工探索*/
else
FindWay(map,1,1);/*系統自動從下標1,1的地方開始探索*/
Result();/*輸出結果*/
Close();
}
void Init(void)/*圖形初始化*/
{
int gd=DETECT,gm;
initgraph(&gd,&gm,"c:\\tc");
}
void DrawPeople(int *x,int *y,int n)/*畫人工控制圖*/
{/*如果將以下兩句注釋掉，則顯示人工走過的路徑，*/
setfillstyle(SOLID_FILL,WHITE); /*設置白色實體填充樣式*/
bar(100+(*y)*15-6,50+(*x)*15-6,100+(*y)*15+6,50+(*x)*15+6);
/*恢復原通路*/
switch(n)/*判斷x,y的變化，8個方向的變化*/
{
case 1: (*x)--;break; /*上*/
case 2: (*x)--;(*y)++;break ;/*右上*/
case 3: (*y)++;break; /*右*/
case 4: (*x)++;(*y)++;break; /*右下*/
case 5: (*x)++;break; /*下*/
case 6: (*x)++;(*y)--;break; /*左下*/
case 7: (*y)--;break; /*左*/
case 8: (*x)--;(*y)--;break; /*左上*/
}
setfillstyle(SOLID_FILL,RED);/*新位置顯示探索物*/
bar(100+(*y)*15-6,50+(*x)*15-6,100+(*y)*15+6,50+(*x)*15+6);
}
void PeopleFind(int (*map)[N])/*人工手動查找*/
{
int x,y;
char c=0;/*接收按鍵的變數*/
x=y=1;/*人工查找的初始位置*/
setcolor(11);
line(500,200,550,200);
outtextxy(570,197,"d");
line(500,200,450,200);
outtextxy(430,197,"a");
line(500,200,500,150);
outtextxy(497,130,"w");
line(500,200,500,250);
outtextxy(497,270,"x");
line(500,200,450,150);
outtextxy(445,130,"q");
line(500,200,550,150);
outtextxy(550,130,"e");
line(500,200,450,250);
outtextxy(445,270,"z");
line(500,200,550,250);
outtextxy(550,270,"c");/*以上是畫8個方向的控制介紹*/
setcolor(YELLOW);
outtextxy(420,290,"Press 'Enter' to end");/*壓回車鍵結束*/
setfillstyle(SOLID_FILL,RED);
bar(100+y*15-6,50+x*15-6,100+y*15+6,50+x*15+6);/*入口位置顯示*/
while(c!=13)/*如果按下的不是回車鍵*/
{
c=getch();/*接收字元後開始各個方向的探索*/
if(c=='w'&&map[x-1][y]!=1)
DrawPeople(&x,&y,1);/*上*/
else
if(c=='e'&&map[x-1][y+1]!=1)
DrawPeople(&x,&y,2);/*右上*/
else
if(c=='d'&&map[x][y+1]!=1)
DrawPeople(&x,&y,3);/*右*/
else
if(c=='c'&&map[x+1][y+1]!=1)
DrawPeople(&x,&y,4);/*右下*/
else
if(c=='x'&&map[x+1][y]!=1)
DrawPeople(&x,&y,5);/*下*/
else
if(c=='z'&&map[x+1][y-1]!=1)
DrawPeople(&x,&y,6); /*左下*/
else
if(c=='a'&&map[x][y-1]!=1)
DrawPeople(&x,&y,7); /*左*/
else if(c=='q'&&map[x-1][y-1]!=1)
DrawPeople(&x,&y,8); /*左上*/
}
setfillstyle(SOLID_FILL,WHITE); /*消去紅色探索物，恢復原迷宮圖*/
bar(100+y*15-6,50+x*15-6,100+y*15+6,50+x*15+6);
if(x==N-2&&y==N-2)/*人工控制找成功的話*/
yes=1; /*如果成功標志為1*/
}
void WayCopy(int (*oldmap)[N],int (*map)[N])/*拷貝迷宮數組 */
{
int i,j;
for(i=0;i<N;i++)
for(j=0;j<N;j++)
oldmap[i][j]=map[i][j];
}
int FindWay(int (*map)[N],int i,int j)/*遞歸找路*/
{
if(i==N-2&&j==N-2)/*走到出口*/
{
yes=1;/*標志為1,表示成功*/
return;
}
map[i][j]=1;/*走過的地方變為1*/
WayCopy(oldmap,map); /*拷貝迷宮圖*/
if(oldmap[i+1][j+1]==0&&!yes)/*判斷右下方是否可走*/
{
FindWay(oldmap,i+1,j+1);
if(yes)/*如果到達出口了，再把值賦給顯示路線的way數組,也正是這個原因,所以具體路線是從最後開始保存*/
{
way[wayn][0]=i;
way[wayn++][1]=j;
return;
}
}
WayCopy(oldmap,map);
if(oldmap[i+1][j]==0&&!yes)/*判斷下方是否可以走,如果標志yes已經是1也不用找下去了*/
{
FindWay(oldmap,i+1,j);
if(yes)
{
way[wayn][0]=i;
way[wayn++][1]=j;
return;
}
}
WayCopy(oldmap,map);
if(oldmap[i][j+1]==0&&!yes)/*判斷右方是否可以走*/
{
FindWay(oldmap,i,j+1);
if(yes)
{
way[wayn][0]=i;
way[wayn++][1]=j;
return;
}
}
WayCopy(oldmap,map);
if(oldmap[i-1][j]==0&&!yes)/*判斷上方是否可以走*/
{
FindWay(oldmap,i-1,j);
if(yes)
{
way[wayn][0]=i;
way[wayn++][1]=j;
return;
}
}
WayCopy(oldmap,map);
if(oldmap[i-1][j+1]==0&&!yes)/*判斷右上方是否可以走*/
{
FindWay(oldmap,i-1,j+1);
if(yes)
{
way[wayn][0]=i;
way[wayn++][1]=j;
return;
}
}
WayCopy(oldmap,map);
if(oldmap[i+1][j-1]==0&&!yes)/*判斷左下方是否可以走*/
{
FindWay(oldmap,i+1,j-1);
if(yes)
{
way[wayn][0]=i;
way[wayn++][1]=j;
return;
}
}
WayCopy(oldmap,map);
if(oldmap[i][j-1]==0&&!yes)/*判斷左方是否可以走*/
{
FindWay(oldmap,i,j-1);
if(yes)
{
way[wayn][0]=i;
way[wayn++][1]=j;
return;
}
}
WayCopy(oldmap,map);
if(oldmap[i-1][j-1]==0&&!yes)/*判斷左上方是否可以走*/
{
FindWay(oldmap,i-1,j-1);
if(yes)
{
way[wayn][0]=i;
way[wayn++][1]=j;
return;
}
}
return;
}
void MapRand(int (*map)[N])/*開始的隨機迷宮圖*/
{
int i,j;
cleardevice();/*清屏*/
randomize(); /*隨機數發生器*/
for(i=0;i<N;i++)
{
for(j=0;j<N;j++)
{
if(i==0||i==N-1||j==0||j==N-1)/*最外面一圈為牆壁*/
map[i][j]=1;
else
if(i==1&&j==1||i==N-2&&j==N-2)/*出發點與終點表示為可走的*/
map[i][j]=0;
else
map[i][j]=random(2);/*其它的隨機生成0或1*/
}
}
}
void PrMap(int (*map)[N])/*輸出迷宮圖*/
{
int i,j;
for(i=0;i<N;i++)
for(j=0;j<N;j++)
if(map[i][j]==0)
{
setfillstyle(SOLID_FILL,WHITE);/*白色為可走的路*/
bar(100+j*15-6,50+i*15-6,100+j*15+6,50+i*15+6);
}
else
{
setfillstyle(SOLID_FILL,BLUE);/*藍色為牆壁*/
bar(100+j*15-6,50+i*15-6,100+j*15+6,50+i*15+6);
}
}
void Find(void)/*找到通路*/
{
int i;
setfillstyle(SOLID_FILL,RED);/*紅色輸出走的具體路線*/
wayn--;
for(i=wayn;i>=0;i--)
{
bar(100+way[i][1]*15-6,50+way[i][0]*15-6,100+
way[i][1]*15+6,50+way[i][0]*15+6);
sleep(1);/*控制顯示時間*/
}
bar(100+(N-2)*15-6,50+(N-2)*15-6,100+
(N-2)*15+6,50+(N-2)*15+6); /*在目標點標紅色*/
setcolor(GREEN);
settextstyle(0,0,2);/*設置字體大小*/
outtextxy(130,400,"Find a way!");
}
void NotFind(void)/*沒找到通路*/
{
setcolor(GREEN);
settextstyle(0,0,2);/*設置字體大小*/
outtextxy(130,400,"Not find a way!");
}
void Result(void)/*結果處理*/
{
if(yes)/*如果找到*/
Find();
else/*沒找到路*/
NotFind();
getch();
}
void Close(void)/*圖形關閉*/
{
closegraph();
}
另外一個，是數據結構的：
#include<stdio.h>
#define NUM 10/* 定義物品總數*/
#define CONTENT 10 /*定義包的容量*/
void knapsack(int v[NUM],int w[NUM],int c,int m[NUM ][CONTENT])
{
int n=NUM-1;
int i,j;
int jMax;
if((w[n]-1)< c)
jMax = w[n]-1;
else
jMax = c;
/* 初始化m[n][j] */
for(j = 0; j <= jMax; j++)
m[n][j] = 0;
for(j = jMax +1; j <= c; j++)
m[n][j] = v[n];
/*使用非遞歸的演算法來求解m[i][j] */
for(i = n-1; i > 0; i--)
{
if((w[i]-1)< c)
jMax = w[i]-1;
else
jMax = c;
for(j = 0; j <= jMax; j++)
m[i][j] = m[i+1][j] ;
for(j = jMax +1; j <= c; j++)
{
if(m[i+1][j] >= (m[i+1][j-w[i]]+v[i]))
m[i][j] = m[i+1][j] ;
else
m[i][j] = m[i+1][j-w[i]]+v[i];
}
}
if(c>w[0])
{
if(m[1][c] >= (m[1][c-w[0]]+v[0]))
m[0][c]= m[1][c];
else
m[0][c]= m[1][c-w[0]]+v[0];
}
else
m[0][c]= m[1][c];
}
/*尋找最優解*/
void traceback(int flag[NUM],int w[NUM],int m[NUM][CONTENT])
{
int n = NUM -1;
int i;
int c = CONTENT;
for(i = 0; i < n; i++)
{
if(m[i][c] == m[i+1][c])
flag[i] = 0;
else
{
flag[i] = 1;
c-=w[i];
}
}
if(m[n][c] >0)
flag[n] = 1;
else
flag[n] = 0;
}
/* 列印最優解*/
void printResult(int flag[NUM],int w[NUM],int v[NUM],int m[NUM][CONTENT])
{
int i;
printf("the knapsack should contain:\n");
printf(" num weight value \n");
for(i = 0;i < NUM; i++)
{
if(flag[i] == 1)
printf(" %d %d %d\n",i,w[i],v[i]);
}
printf("the max value in the knapsack is: %d\n",m[0][CONTENT]);
}
int main()
{
int value[NUM]={5,2,3,4,3,6,5,7,8,2};
int weight[NUM]={2,1,3,2,4,3,5,6,2,2};
int c = CONTENT;
int maxvalue[NUM][CONTENT];
int flag[NUM]={0,0,0,0,0,0,0,0,0,0};
clrscr();
printf("****************************************\n");
printf("* this program will solve *\n");
printf("* the problem of 0-1knapsack *\n");
printf("****************************************\n");
/*計算最優值*/
knapsack(value,weight,c,maxvalue);
/*構造最優解*/
traceback(flag,weight,maxvalue);
/*列印程序的結果*/
printResult(flag,weight,value,maxvalue);
getch();
return 0;
}