#include <stdio.h>
#include <stdlib.h>
#define MaxRow 10
#define MaxCol 10
#define MAXSTACKSIZE 100
#define STACKINCREMENT 10
#define NOENOUGHROOM 10
#define STACKOVERFLOW 11
#define up 1
#define down 2
#define left 3
#define right 4
typedef struct {
int *abscissa;
int *ordinate;
int *direction;
int maxstacksize;
}SqStack;
SqStack Stack;
int top = -1; //初始化棧頂
//依次上下左右行走
int arrowx[4] = {0, 0, -1, 1};
int arrowy[4] = {-1, 1, 0, 0};
int Maze[MaxRow][MaxCol] = {}; //用來標記走過的路
int pathMaze[MaxRow][MaxCol] = {}; //用來存儲正確路徑
int maxabs = 1, maxord = 1; //用戶輸入的迷宮大小
void InitStack() {
int *absbase, *ordbase, *direbase;
absbase = (int *)malloc(MAXSTACKSIZE*sizeof(int));
ordbase = (int *)malloc(MAXSTACKSIZE*sizeof(int));
direbase = (int *)malloc(MAXSTACKSIZE*sizeof(int));
if(!absbase || !ordbase || !direbase)
exit(NOENOUGHROOM);
Stack.abscissa = absbase;
Stack.ordinate = ordbase;
Stack.direction = direbase;
Stack.maxstacksize = MAXSTACKSIZE;
}
void push(int abscissa, int ordinate, int direction) {
++top;
//判斷是否溢出
if(top >= Stack.maxstacksize){
int *newabsbase, *newordbase, *newdirebase;
newabsbase = (int *)realloc(Stack.abscissa, (MAXSTACKSIZE + STACKINCREMENT)*sizeof(int));
newordbase = (int *)realloc(Stack.ordinate, (MAXSTACKSIZE + STACKINCREMENT)*sizeof(int));
newdirebase = (int *)realloc(Stack.direction, (MAXSTACKSIZE +STACKINCREMENT)*sizeof(int));
if(!newordbase || !newabsbase || !newdirebase)
exit(NOENOUGHROOM);
Stack.abscissa = newabsbase;
Stack.ordinate = newordbase;
Stack.direction = newdirebase;
}
*(Stack.abscissa + top) = abscissa;
*(Stack.ordinate + top) = ordinate;
*(Stack.direction + top -1) = direction;
}
void pop() {
//判斷是否溢出
if(top == -2)
exit(STACKOVERFLOW);
*(Stack.abscissa + top) = 0;
*(Stack.ordinate + top) = 0;
*(Stack.direction + top) = 0;
--top;
}
//打印點和方向
void printPointAndDirection(int n) {
switch (*(Stack.direction + n)) {
case up:
printf("(%d, %d, up)\n", *(Stack.abscissa + n), *(Stack.ordinate + n));
break;
case down:
printf("(%d, %d, down)\n", *(Stack.abscissa + n), *(Stack.ordinate + n));
break;
case left:
printf("(%d, %d, left)\n", *(Stack.abscissa + n), *(Stack.ordinate + n));
break;
case right:
printf("(%d, %d, right)\n", *(Stack.abscissa + n), *(Stack.ordinate + n));
break;
}
}
//打印迷宮解
void printPath() {
printf("輸出路線:\n");
int i = 0;
while(1) {
printPointAndDirection(i);
if(*(Stack.abscissa + i) == maxabs && *(Stack.ordinate + i) == maxord)
break;
++i;
}
}
//標記走過的路
void markMaze(int abscissa, int ordinate) {
Maze[ordinate][abscissa] = 2;
pathMaze[ordinate][abscissa] = 2;
}
//打印迷宮并標出正確出路
void printPathMaze() {
printf("\n迷宮輸出是:\n");
for(int i = 1;i <= maxord;i++) {
for(int j = 1;j <= maxabs;j++) {
printf("%d ", pathMaze[i][j]);
}
printf("\n");
}
printf("\n\n");
}
//打印用來做標記的迷宮
void printMaze() {
printf("\n迷宮輸出是:\n");
for(int i = 1;i <= maxord;i++) {
for(int j = 1;j <= maxabs;j++) {
printf("%d ", Maze[i][j]);
}
printf("\n");
}
printf("\n\n");
}
//初始化迷宮
void InitMaze() {
printf("\n請輸入迷宮的長和寬:\n");
scanf("%d %d", &maxabs, &maxord);
printf("請輸入迷宮:\n");
for(int i = 1;i <= maxord;i++) {
for(int j = 1;j <= maxabs;j++) {
scanf("%d", &Maze[i][j]);
pathMaze[i][j] = Maze[i][j];
}
}
}
//尋找出路
void runMaze() {
//判斷第一個方向
push(1, 1 , 0);
markMaze(1, 1);
int flag = 0;
while(1) {
int xNow, yNow;
int i = 0;
xNow = *(Stack.abscissa + top);
yNow = *(Stack.ordinate + top);
if(xNow == maxabs && yNow == maxord) {
flag = 1;
break;
}else if(top == -2)
break;
for(i = 0;i < 4;i++) {
int xNext, yNext;
xNext = xNow + arrowx[i];
yNext = yNow + arrowy[i];
//找到可走的點
if(xNext > 0 && xNext <= maxabs && yNext > 0 && yNext <= maxord && Maze[yNext][xNext] == 0) {
push(xNext, yNext, i+1);
markMaze(xNext, yNext);
break;
}
}
//無路可走
if(i == 4) {
pathMaze[yNow][xNow] = 0;
pop();
}
}
if(flag) {
printPath();
printPathMaze();
} else {
printf("\n沒有出路庐冯,無解!\n");
}
}
int main() {
InitMaze();
runMaze();
}
用棧實現(xiàn)迷宮求解(改進版礁凡,C語言)
最后編輯于 :
?著作權歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
- 文/潘曉璐 我一進店門搔耕,熙熙樓的掌柜王于貴愁眉苦臉地迎上來,“玉大人痰娱,你說我怎么就攤上這事弃榨。” “怎么了梨睁?”我有些...
- 文/不壞的土叔 我叫張陵鲸睛,是天一觀的道長。 經(jīng)常有香客問我坡贺,道長官辈,這世上最難降的妖魔是什么? 我笑而不...
- 正文 為了忘掉前任遍坟,我火速辦了婚禮拳亿,結(jié)果婚禮上,老公的妹妹穿的比我還像新娘愿伴。我一直安慰自己肺魁,他們只是感情好,可當我...
- 文/花漫 我一把揭開白布隔节。 她就那樣靜靜地躺著鹅经,像睡著了一般寂呛。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上瘾晃,一...
- 文/蒼蘭香墨 我猛地睜開眼阀圾,長吁一口氣:“原來是場噩夢啊……” “哼哪廓!你這毒婦竟也來了?” 一聲冷哼從身側(cè)響起初烘,我...
- 正文 年R本政府宣布,位于F島的核電站撑蒜,受9級特大地震影響歹啼,放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜座菠,卻給世界環(huán)境...
- 文/蒙蒙 一狸眼、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧辈灼,春花似錦份企、人聲如沸。這莊子的主人今日做“春日...
- 文/蒼蘭香墨 我抬頭看了看天上的太陽甜紫。三九已至,卻和暖如春骂远,著一層夾襖步出監(jiān)牢的瞬間囚霸,已是汗流浹背。 一陣腳步聲響...
推薦閱讀更多精彩內(nèi)容
- ~~~ /** * 1 從maze.txt讀入迷宮 * 2 從入口坐標(1,1)尋找到出口的通路 * 3 顯示迷宮...
- /** * 用不帶頭結(jié)點的單鏈表構(gòu)造的鏈式棧 * LinkedStack * 創(chuàng)建人:guxiaohao * 時間...
- 2016年第二周十大熱播節(jié)目: 2016年第一周十大熱播節(jié)目: 2015年12月十大熱播電臺節(jié)目精選愧膀,圖片來自后臺...