通过栈实现迷宫的解问题

代码实现:

#include #include <graphics.h> #include <Windows.h> #include

using namespace std;

#define IsValid(row,col) (row >= 0 && row < ROW && col >= 0 && col < COL)

#define SCREEN_WIDTH 640 #define SCRREN_HEIGHT 640

#define ROW 6 #define COL 6

#define RATIO 80 //偏移值

typedef enum _STATUS { WALL, //墙 FLOOR, //空地 MAN, //人

ALL //所有

}_STATUS;

typedef struct _MAN { int row; int col; //主角的位置行列 }_MAN;

//地图 int map[3][ROW][COL] = { {{0,0,2,0,0,0}, {0,0,1,1,1,0}, {0,0,1,0,0,0}, {0,1,1,1,1,0}, {0,0,1,0,1,0}, {0,0,0,0,1,0}},

{{0,0,2,0,0,0}, {0,0,1,0,1,0}, {0,1,1,1,0,0}, {0,1,0,1,1,0}, {0,0,1,0,1,1}, {0,0,1,0,0,0}}, {{0,0,2,0,0,0}, {0,1,1,0,1,0}, {0,1,0,1,0,0}, {0,0,1,1,1,0}, {0,0,1,1,1,1}, {0,0,0,0,1,0}}

};

//初始化界面 void InitMenu(IMAGE *images,int n) { if (!images) return;

loadimage(&images[WALL], _T("wall_right.bmp"), RATIO, RATIO); //加载墙的图片 loadimage(&images[FLOOR], _T("floor.bmp"), RATIO, RATIO); //加载空地的图片 loadimage(&images[MAN], _T("man.bmp"), RATIO, RATIO); //加载人物的图片 //初始化画布 initgraph(SCREEN_WIDTH, SCRREN_HEIGHT); //加载地图背景 IMAGE blackground; loadimage(&blackground, _T("blackground.bmp"), SCREEN_WIDTH, SCRREN_HEIGHT); putimage(0, 0, &blackground); //根据地图绘制图片 for (int i = 0; i < ROW; i++) { for (int j = 0; j < COL; j++) { if (map[n][i][j] == WALL) { putimage(RATIO + j * RATIO, RATIO + i * RATIO, &images[WALL]); } else if (map[n][i][j] == FLOOR) { putimage(RATIO + j * RATIO, RATIO + i * RATIO, &images[FLOOR]); } else if (map[n][i][j] == MAN) { putimage(RATIO + j * RATIO, RATIO + i * RATIO, &images[MAN]); } } }

}

bool IsValidEdit(_MAN cur,_MAN man,int n) { if (IsValid(man.row, man.col) && (cur.row != man.row || cur.col != man.col) && (cur.row == 0 || cur.row == ROW - 1 || cur.col == 0 || cur.col == COL -1) && map[n][cur.row][cur.col] == MAN) { return true; } else { return false; } }

bool IsValidNext(_MAN next,int n) { if (IsValid(next.row, next.col) && map[n][next.row][next.col] == FLOOR) { return true; } else { return false; } }

void draw(_MAN next,_MAN cur,int n) { IMAGE Man, Floor; loadimage(&Man, _T(“man.bmp”), RATIO, RATIO); //加载墙的图片 loadimage(&Floor, _T(“floor.bmp”), RATIO, RATIO); //加载空地的图片

map[n][next.row][next.col] = MAN; putimage(RATIO + next.col * RATIO, RATIO + next.row * RATIO, &Man); map[n][cur.row][cur.col] = 3; putimage(RATIO + cur.col * RATIO, RATIO + cur.row * RATIO, &Floor); //每次绘制延时1S Sleep(500);

}

void gameStart(int n) {

_MAN man = { 0,2 }; //主角的起始位置 //出入站 stack<_MAN> stack; //首位值入栈 stack.push(man); IMAGE img; //延时1s开始 settextcolor(RED); //设置红色

​ settextstyle(30, 0, _T(“微软雅黑”));

outtextxy(230, 20, _T("2秒后开始自动寻路")); Sleep(2000); outtextxy(230, 20, _T("正在开始寻路ing......")); while (!stack.empty()) { _MAN cur = stack.top(); //获取栈顶元素 _MAN next = cur; //栈顶元素下个值 if (IsValidEdit(cur,man,n)) { //找到出口 break; } //向上 next = cur; next.row -= 1; if (IsValidNext(next,n)) { stack.push(next); //入栈 draw(next, cur,n); // map[next.row][next.col] == 3; continue; } //向左 next = cur; next.col -= 1; if (IsValidNext(next,n)) { stack.push(next); //入栈 //绘制图形 draw(next, cur,n); //map[next.row][next.col] == 3; continue; } //向右 next = cur; next.col += 1; if (IsValidNext(next,n)) { stack.push(next); //入栈 draw(next, cur,n); //map[next.row][next.col] == 3; continue; } //向下 next = cur; next.row += 1; if (IsValidNext(next,n)) { stack.push(next); //入栈 draw(next, cur,n); // map[next.row][next.col] == 2; continue; } //出栈 stack.pop(); if (stack.empty()) { //关闭图形 closegraph(); printf("没有找到终点路径!\n"); return; } next = stack.top(); draw(next, cur,n); } //延时1S Sleep(1000); //清除屏幕设备 cleardevice(); settextstyle(40, 0, _T("微软雅黑")); outtextxy(220, 260, _T("3秒后游戏结束")); Sleep(3000); //关闭图形 closegraph(); printf("\n输出地图后端图形:\n\n"); for (int i = 0; i < ROW; i++) { for (int j = 0; j < COL; j++) { cout << map[n][i][j] << ' '; } printf("\n"); } printf("\n"); cout << "任意键进入下一关!\n\n"; system("pause");

}

int main(void) { IMAGE images[ALL];

int n = 3; for (int i = 0; i < n; i++) { //游戏开始 InitMenu(images, i); gameStart(i); } system("pause"); return 0;

}