c語言迷宮演算法

❶ 如何用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語言中用棧實現迷宮問題

#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;
}
滿意請採納！

❸ C語言迷宮問題，求該演算法的時間和空間的復雜度。迷宮的路徑已經定義好，求出路的演算法。

該演算法是不穩定的，其時空復雜度不僅和m,n有關，還和mg[][]的具體數值有關。
最壞情況下：每個點都試探過才走到終點。此時時間復雜度為：(m*n-1)*4，（其中4為4個方向），空間復雜度m*n*2，(其中m*n為存儲迷宮圖空間，m*n為棧空間);
再好情況下：一次試探過就走到終點。此時時間復雜度為：(min(m,n)-1)，空間復雜度m*n;

所以：
該演算法時間復雜度為：[(m*n-1)*4+(min(m,n)-1)]/2，約為2×m×n
空間復雜度為3*m*n/2

❹ 數據結構與演算法作業：用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語言，用二維數組解決迷宮問題。來段完整的代碼吧。

好的，以下是使用二維數組解決迷宮問題的C語言代碼示例：

Copy code
#include <stdio.h>

#define ROW 6 // 迷宮行數
#define COL 6 // 迷宮列數

int maze[ROW][COL] = { // 迷宮地圖 1表兄銀碰示障礙，0表示通路
{1, 1, 1, 1, 1, 1},
{1, 0, 0, 1, 0, 1},
{1, 0, 0, 1, 0, 1},
{1, 0, 0, 0, 0, 1},
{1, 0, 1, 1, 0, 1},
{1, 1, 1, 1, 1, 1},
};

int result[ROW][COL]; // 存放走迷宮的結果

int dfs(int row, int col) {
if (row == ROW - 1 && col == COL - 1) { // 到達終點
result[row][col] = 1;
return 1;
}
if (maze[row][col] == 0) { // 當前位置是通路
result[row][col] = 1;
if (row < ROW - 1 && dfs(row + 1, col)) { // 向下走有解
return 1;
}
if (col < COL - 1 && dfs(row, col + 1)) { // 向右走有解
return 1;
}
result[row][col] = 0; // 標記走過的路
}
return 0; // 返回無解羨談
}

void print_result() {
printf("走迷宮的結果：\n");
for (int i = 0; i < ROW; i++) {
for (int j = 0; j < COL; j++) {
printf("%d ", result[i][j]);
}
printf("\n");
}
}

int main() {
if (dfs(0, 0)) { // 從起點開始走迷宮
print_result();
} else {
printf("無法走出迷宮！\n");
}
return 0;
}
上述搏碰代碼中，我們使用了一個二維數組 maze 來表示迷宮地圖，其中 1 表示障礙，0 表示通路；另一個二維數組 result 用來存儲走迷宮的結果，其中 1 表示該位置走通了， 0 表示該位置沒有走通。

我們使用 dfs 函數來進行深度優先搜索，從起點 (0, 0) 開始往下、往右走，直到走到終點 (ROW-1, COL-1)，如果存在通路，則將路徑標記在 result 數組中，並返回 1，否則返回 0 表示無解。

最後，我們在 main 函數中調用 dfs 函數，判斷是否能從起點走出迷宮，如果有解，則輸出走迷宮的結果；否則，輸出 "無法走出迷宮" 的提示。

❻ 求解c語言一遞歸迷宮問題

給你給偽演算法：（設坐標為x,y,坐標向右和下延生。）
函數：
｛
判斷當前是不是（7,7)，如果是，表示走出迷宮。列印軌跡
1 嘗試往左先走一步（x-1，如果x小於0，或者對應位置標識為阻塞）
2 1如果成功，用本函數遞歸調用左走一步的坐標，並記下當前位置到軌跡列表。
3 嘗試往前先走一步（y+1，如果y小於0，或者對應位置標識為阻塞）
4 3如果成功，用本函數遞歸調用前走一步的坐標,並記下當前位置到軌跡列表。
5 嘗試往右先走一步（x+1，如果x小於0，或者對應位置標識為阻塞）
6 5如果成功，用本函數遞歸調用前走一步的坐標,並記下當前位置到軌跡列表。
如果是（0，0），表示沒有合適的路徑可走出迷宮。
如果不是（0，0），將軌跡列表最後一位彈出。
｝

❼ 迷宮問題，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 不一定完全對。也許有小錯誤。有問題可以來問我哈