拼搏

拼搏

跪求老鼠走迷宫游戏，必须用C++编写，用栈来实现，因为是数据结构课程设计所以只要现成代码，越快越好。_走迷宫编程怎么做

admin

本文目录一览

关于C++迷宫问题，寻找一条通路穿越迷宫（找到一条即可）。要求写出一个递归程序来穿越迷宫。

跪求老鼠走迷宫游戏，必须用C++编写，用栈来实现，因为是数据结构课程设计所以只要现成代码，越快越好。_走迷宫编程怎么做-第1张-游戏相关-拼搏

题目有问题：如何指定迷宫的起点和终点。

我这里假设迷宫某个边界位置是起点，(x, y)是否是终点要用GotGoal(x, y)函数判断。


核心函数

void DFS(char *m, int height, int width, int x, int y, int now_dir)


这里m是一个一维数组，表示迷宫。格点x, y的信息是m[y * width + x]

比如3行4列的迷宫

####

#...

..##

在m里就是#####.....##，每一行紧接着上一行。


height 迷宫高度

width 迷宫宽度


x是当前位置横坐标。右边是正方向。


y是当前位置纵坐标。下方是正方向。


now_dir是是当前的方向。你需要给上下左右4个方向规定一个编号。

比如

int?dir_list[4][2]?=?{
????{-1,?0},?//?地图左
????{0,?-1},?//?地图上
????{1,?0},??//?地图右
????{0,?1}???//?地图下
};
//?第一个数表示恒坐标变化量，第二个数表示纵坐标变化量

那么对于当前方向now_dir，“摸着右手边的墙”的探索方向编号依次是（可以参照上面dir_list的注释来理解）

(now_dir + 1) % 4 当前方向右侧

(now_dir + 0) % 4 当前方向

(now_dir - 1 + 4) % 4 当前方向左侧

(now_dir - 2 + 4) % 4 当前方向反方向（回头）。（这里要+4是为了防止now_dir减去数字后变成负数，负数除以4的余数还是负数）。


使用DFS的方法：

先将地图信息保存到char数组里，作为DFS函数第一参数

将迷宫入口横坐标保存到x参数，纵坐标保存到y参数

将刚进入迷宫的方向的编号（dir_list的第一下标）保存到now_dir


DFS的基本实现（伪代码）

void?DFS(char?*m,?int?height,?int?width,?int?x,?int?y,?int?now_dir)
{
????int?turn?=?0;
????int?new_dir;
????int?new_x;
????int?new_y;
????if?(GotGoal(x,?y)?)?//?如果当前位置是终点
????????return;
????m[y?*?width?+?x]?=?'X';?//?占据当前位置
????PrintMap(m,?height,?width);?//?打印地图当前状态
????for?(turn?=?1;?=?-2;?turn--)?//?依次循环4个方向：右、前、左、回头
????{
????????new_dir?=?(now_dir?+?turn?+?4)?%?4;?//?计算新方向的编号
????????new_x?=?x?+?dir_list[new_dir][0];
????????new_y?=?y?+?dir_list[new_dir][1];?//?计算出“如果要走新方向，则下一步的位置”
????????if?(new_x??0?||?new_x?=?width)//?如果走出左右边界
????????????continue;
????????if?(new_y??0?||?new_y?=?height)?//?如果走出上下边界
????????????continue;
????????if?('#'?==?m[new_y?*?width?+?new_x])?//?如果下一步是是墙
????????????continue;
????????DFS(m,?height,?width,?new_x,?new_y,?new_dir);
????}
????return;
}


注意：

这个问题由于不涉及最短路，而且每走一步都算走过，包括走进了死胡同。因此这个问题完全不需要用递归，实际上程序也不可能回溯，因为每一步都是对的。直接用for或while循环就行了。用递归，当路线比较长时，可能超过操作系统限制而报错。

对于有环路的迷宫，程序会死循环。

如果要判断出死循环的情况，需要一个额外的数组int m_arrived[][4]，保存每个位置的每个方向是否走过。一开始都是0，走过m[i]且方向是dir的时候，m_arrived[i][dir] = 1即可。

有不明白的地方请追问。

急急急，高手帮帮我啊！用C++编 迷宫旅行。

#includestdio.h
#includegraphics.h
#includeconio.h

typedef struct{
int x,y;
int dir;
}pos,elem;

typedef struct{
elem* b,* t;
int size;
}stack;

void initstack(stack* s)
{
s-b=(elem*)malloc(50*sizeof(elem));
if(s-b){
s-t=s-b;
s-size=50;
return;
}
exit(0);
}
void push(stack* s,elem* e)
{
*s-t=*e;
s-t++;
}
void pop(stack* s,elem* e)
{
*e=*--s-t;
}
void gettop(stack* s,elem* e)
{
*e=*(s-t-1);
}
void clearstack(stack* s)
{
s-t=s-b;
}
int stackempty(stack* s)
{
return !(s-t-s-b);
}
int destroystack(stack* s)
{
free(s-b);
free(s);
return 1;
}
int mg[10][10]={
{-1,-0,-1,-1,-1,-1,-1,-1,-1,-1},
{-1,-0,-0,-0,-1,-0,-0,-0,-0,-1},
{-1,-0,-1,-0,-1,-0,-1,-1,-0,-1},
{-1,-0,-1,-1,-0,-0,-0,-0,-0,-1},
{-1,-0,-0,-1,-0,-1,-1,-0,-0,-1},
{-1,-0,-0,-0,-0,-0,-1,-0,-0,-1},
{-1,-0,-1,-0,-0,-0,-0,-1,-0,-1},
{-1,-0,-1,-1,-0,-0,-0,-1,-0,-1},
{-1,-0,-0,-0,-1,-0,-0,-1,-0,-0},
{-1,-1,-1,-1,-1,-1,-1,-1,-1,-1}
};

void step(stack* s,pos* cur,stack* result);
void savepath(stack* s,pos* cur,stack* result);
void draw(int y,int x);

void step(stack* s,pos* cur,stack* result)
{
if(stackempty(result)||s-t-s-bresult-t-result-b){
for(cur-dir++;cur-dir5;cur-dir++){
setfillstyle(SOLID_FILL,15);
switch(cur-dir){
case 1:
if(!mg[cur-y-1][cur-x]){
mg[cur-y][cur-x]=1;
push(s,cur);
cur-y--;
cur-dir=0;
draw(cur-y,cur-x);
return;
}
break;
case 2:
if(!mg[cur-y][cur-x+1]){
mg[cur-y][cur-x]=1;
push(s,cur);
cur-x++;
cur-dir=0;
draw(cur-y,cur-x);
return;
}
break;
case 3:
if(!mg[cur-y+1][cur-x]){
mg[cur-y][cur-x]=1;
push(s,cur);
cur-y++;
cur-dir=0;
draw(cur-y,cur-x);
return;
}
break;
case 4:
if(!mg[cur-y][cur-x-1]){
mg[cur-y][cur-x]=1;
push(s,cur);
cur-x--;
cur-dir=0;
draw(cur-y,cur-x);
return;
}
break;
default:
exit(0);
}
}
}
mg[cur-y][cur-x]=0;
setfillstyle(SOLID_FILL,0);
draw(cur-y,cur-x);
pop(s,cur);
}

void savepath(stack* s,pos* cur,stack* result)
{
pos* top=s-t;
if(stackempty(result)){
push(result,cur);
while(tops-b)
push(result,--top);
}
else if(result-t-result-bs-t-s-b){
clearstack(result);
push(result,cur);
while(tops-b)
push(result,--top);
}
}

void draw(int y,int x)
{
bar(100+15*x,100+15*y,115+15*x,115+15*y);
}

void main(void)
{
int i;
int x,y;
int gd=DETECT,gm;
stack* s=NULL;
stack* result=NULL;
pos* cur=NULL;

initgraph(gd,gm,"");
for(x=0;x10;x++)
for(y=0;y10;y++){
if(mg[y][x]){
setfillstyle(SOLID_FILL,3);
draw(y,x);
}
}

result=(stack*)malloc(sizeof(stack));
initstack(result);
s=(stack*)malloc(sizeof(stack));
cur=(pos*)malloc(sizeof(pos));
initstack(s);
cur-x=1;
cur-y=0;
cur-dir=0;
push(s,cur);
cur-x=1;
cur-y=1;
cur-dir=1;
do{
if(cur-x==9cur-y==8)
savepath(s,cur,result);
step(s,cur,result);
}while(!stackempty(s));
if(stackempty(result))
printf("no way available");
else{
int ch=0;
printf("following is the shortest path:\n");
while(!stackempty(result)){
pop(result,cur);
setfillstyle(SOLID_FILL,15);
draw(cur-y,cur-x);
if(ch5){
putchar('\n');
ch=0;
}
printf("(%d,%d,%d) ",cur-x,cur-y,cur-dir);
ch++;
}
}
printf("\n");
destroystack(s);
destroystack(result);
free(cur);
printf("Press any key to end");
while(!kbhit());
closegraph();
}

跪求老鼠走迷宫游戏，必须用C++编写，用栈来实现，因为是数据结构课程设计所以只要现成代码，越快越好。

#include "stdafx.h"

#include stack

using namespace std;

const int rows = 8,cols = 8;

HINSTANCE hInst;

HBITMAP ball;

HDC hdc,mdc,bufdc;

HWND hWnd;

DWORD tPre,tNow;

char *str;

int nowPos,prePos;

bool find;

stackint path;


int mapIndex[rows*cols] = { 0,2,0,0,0,0,0,0, ? //材1#59049;

0,1,0,1,1,1,1,0, ? //材2#59049;

0,1,0,1,0,1,1,0, ? //材3#59049;

0,1,0,0,0,1,1,0, ? //材4#59049;

0,1,1,1,1,1,1,0, ? //材5#59049;

0,1,0,0,0,0,1,0, ? //材6#59049;

0,0,1,1,1,1,1,0, ? //材7#59049;

0,0,0,0,0,0,3,0 }; //材8#59049;

int ?record[rows*cols];

ATOM MyRegisterClass(HINSTANCE hInstance);

BOOL InitInstance(HINSTANCE, int);

LRESULT CALLBACK WndProc(HWND, UINT, WPARAM, LPARAM);

void MyPaint(HDC hdc);


int APIENTRY WinMain(HINSTANCE hInstance,

? ? ? ? ? ? ? ? ? ? ?HINSTANCE hPrevInstance,

? ? ? ? ? ? ? ? ? ? ?LPSTR ? ? lpCmdLine,

? ? ? ? ? ? ? ? ? ? ?int ? ? ? nCmdShow)

{

MSG msg;


MyRegisterClass(hInstance);



if (!InitInstance (hInstance, nCmdShow))?

{

return FALSE;

}


? ? while( msg.message!=WM_QUIT )

? ? {

? ? ? ? if( PeekMessage( msg, NULL, 0,0 ,PM_REMOVE) )

? ? ? ? {

? ? ? ? ? ? TranslateMessage( msg );

? ? ? ? ? ? DispatchMessage( msg );

? ? ? ? }

else

{

tNow = GetTickCount();

if(tNow-tPre = 100)

MyPaint(hdc);

}

? ? }

return msg.wParam;

}


//****注册窗口*************************

ATOM MyRegisterClass(HINSTANCE hInstance)

{

WNDCLASSEX wcex;


wcex.cbSize = sizeof(WNDCLASSEX);?

wcex.style = CS_HREDRAW | CS_VREDRAW;

wcex.lpfnWndProc = (WNDPROC)WndProc;

wcex.cbClsExtra = 0;

wcex.cbWndExtra = 0;

wcex.hInstance = hInstance;

wcex.hIcon = NULL;

wcex.hCursor = NULL;

wcex.hCursor = LoadCursor(NULL, IDC_ARROW);

wcex.hbrBackground = (HBRUSH)(COLOR_WINDOW+1);

wcex.lpszMenuName = NULL;

wcex.lpszClassName = "canvas";

wcex.hIconSm = NULL;


return RegisterClassEx(wcex);

}


//****初始化*************************************


BOOL InitInstance(HINSTANCE hInstance, int nCmdShow)

{

HBITMAP bmp;

hInst = hInstance;


hWnd = CreateWindow("canvas", "迷宫" , WS_OVERLAPPEDWINDOW,

CW_USEDEFAULT, 0, CW_USEDEFAULT, 0, NULL, NULL, hInstance, NULL);


if (!hWnd)

{

return FALSE;

}


MoveWindow(hWnd,10,10,430,450,true);

ShowWindow(hWnd, nCmdShow);

UpdateWindow(hWnd);

hdc = GetDC(hWnd);

mdc = CreateCompatibleDC(hdc);

bufdc = CreateCompatibleDC(hdc);


bmp = CreateCompatibleBitmap(hdc,cols*50,rows*50);

SelectObject(mdc,bmp);


HBITMAP tile;

int rowNum,colNum;

int i,x,y;


tile = (HBITMAP)LoadImage(NULL,"tile.bmp",IMAGE_BITMAP,50,50,LR_LOADFROMFILE);

ball = (HBITMAP)LoadImage(NULL,"ball.bmp",IMAGE_BITMAP,50,50,LR_LOADFROMFILE);


for (i=0;irows*cols;i++)

{

record[i] = mapIndex[i];


rowNum = i / cols;

colNum = i % cols;

x = colNum * 50;

y = rowNum * 50;

SelectObject(bufdc,tile);


if(!mapIndex[i])

BitBlt(mdc,x,y,50,50,bufdc,0,0,SRCCOPY);

else

{

? if(mapIndex[i] == 2)

{

nowPos = i;

path.push(i);

record[i] = 0;

}

BitBlt(mdc,x,y,50,50,bufdc,0,0,WHITENESS);

}

}

prePos = cols * rows + 1;


MyPaint(hdc);


return TRUE;

}


//****核心代码*********************************

void MyPaint(HDC hdc)

{

int rowNum,colNum;

int x,y;

int up,down,left,right;



rowNum = prePos / cols;

colNum = prePos % cols;

x = colNum * 50;

y = rowNum * 50;


SelectObject(bufdc,ball);

BitBlt(mdc,x,y,50,50,bufdc,0,0, WHITENESS);



rowNum = nowPos / cols;

colNum = nowPos % cols;

x = colNum * 50;

y = rowNum * 50;


SelectObject(bufdc,ball);

BitBlt(mdc,x,y,50,50,bufdc,0,0, SRCCOPY);


if(!find)

{

str = "迷宫入口";


up ? ?= nowPos - cols;

down ?= nowPos + cols;

left ?= nowPos - 1;

right = nowPos + 1;


if(up=0 record[up])

{

path.push(up);

record[up] = 0;

prePos = nowPos;

nowPos = up;


? ? ? ? if(mapIndex[nowPos] == 3)

find = true;

}

else if(down=cols*rows-1 record[down])?

{

path.push(down);

record[down] = 0;

prePos = nowPos;

nowPos = down;


if(mapIndex[nowPos] == 3)

find = true;

}

else if(left=rowNum*cols record[left]) ?

{

path.push(left);

record[left] = 0;

prePos = nowPos;

nowPos = left;


if(mapIndex[nowPos] == 3)

find = true;

}

else if(right=(rowNum+1)*cols-1 record[right]) ?

{

path.push(right);

record[right] = 0;

prePos = nowPos;

nowPos = right;


if(mapIndex[nowPos] == 3)

find = true;

}

else

{

if(path.size() = 1) //#59076;#59343;#58864;#58892;

str = "xxxxx";

else

{

path.pop();

prePos = nowPos;

nowPos = path.top();

}

}

}

else

{

str = "找到出口";

}


TextOut(mdc,0,0,str,strlen(str));

BitBlt(hdc,10,10,cols*50,rows*50,mdc,0,0,SRCCOPY);


tPre = GetTickCount();

}


//****消息函数***********************************

LRESULT CALLBACK WndProc(HWND hWnd, UINT message, WPARAM wParam, LPARAM lParam)

{

switch (message)

{

case WM_KEYDOWN:

if(wParam==VK_ESCAPE)

PostQuitMessage(0);

break;

case WM_DESTROY:

DeleteDC(mdc);

DeleteDC(bufdc);

DeleteObject(ball);


ReleaseDC(hWnd,hdc);


PostQuitMessage(0);

break;

default:

return DefWindowProc(hWnd, message, wParam, lParam);

? ?}

? ?return 0;

}



// ?可以运行 ? 请采纳 ??

有不懂的可以联系我

这个可是标准c++的 ? 这是结果

这是源代码?

数据结构算法 用C++ 迷宫最短路径

一般迷宫寻路可以用递归的算法，或者用先进后出的栈数据结构实现

用的是深度优先的算法，可以寻找到走出迷宫的路径


但本题要求求出最短的路径，这就要使用广度优先的算法

一般在程序中需要用到先进先出的队列数据结构


下面是程序的代码，主要原理是用到

quei，quej和prep三个数组来构成队列

分别储存路径的行，列坐标和上一个节点在队列中的位置


大致算法如下，右三个嵌套的循环实现


首先是第一个节点进入队列

当队列不空（循环1）

｛

? ? ?遍历队列中每节点(循环2）

????｛

? ? ?????将八个方向能够走的节点加入队列（循环3）

???? ｝

? ? ?旧的节点出列

｝


#includeiostream
#includectime?
using?namespace?std;?

#define?MAXNUM?50

void?main()?
{
int?m,n,i,j,x;
cout"请输入迷宫大小"endl;
cinmn;
int?maze[MAXNUM][MAXNUM];

srand((int)time(NULL));
for(i=0;i=m+1;i++){
for(j=0;j=n+1;j++){
if(i==0||j==0||i==m+1||j==n+1)
maze[i][j]=1;
else
{
x=rand()%1000;
if(x700){maze[i][j]=1;}?//控制矩阵中1的个数，太多1迷宫很容易走不通
else{maze[i][j]=0;}
}
coutmaze[i][j]'?';
}
coutendl;
}

//以上是输入和迷宫生成，一下是走迷宫


????int?move[8][2]={0,1,1,0,0,-1,-1,0,1,1,-1,1,-1,-1,1,-1};
int?*quei=new?int[m*n];//储存行坐标队列
int?*quej=new?int[m*n];//储存列坐标队列
int?*prep=new?int[m*n];//储存之前一步在队列中的位置
int?head,rear,length;//队列头，队列尾，队列长度
head=0;rear=1;length=1;
quei[head]=1;quej[head]=1;prep[head]=-1;//入口位置进队列

int?pos;//当前节点在队列中的位置，
int?ii,jj,ni,nj;//当前节点的坐标，新节点的坐标
int?dir;//移动方向

if(maze[1][1]==1)length=0;//第一点就不能通过
else?maze[1][1]=1;


while(length)//队列非空继续
{
for(pos=head;poshead+length;pos++)//寻找这一层所有节点
{
ii=quei[pos];jj=quej[pos];//当前位置坐标
if(ii==mjj==n)break;
for(dir=0;dir8;dir++)//寻找8个方向
{
ni=ii+move[dir][0];nj=jj+move[dir][1];//新坐标
if(maze[ni][nj]==0)//如果没有走过
{
quei[rear]=ni;quej[rear]=nj;prep[rear]=pos;//新节点入队
rear=rear+1;
maze[ni][nj]=1;//标记已经走过
}
}
}
if(ii==mjj==n)break;
head=head+length;
length=rear-head;//这一层节点出列
}

if(ii==mjj==n)
{
while(pos!=-1)
{
cout'('quei[pos]','quej[pos]')';
pos=prep[pos];
if?(pos!=-1)cout',';
}
}
else
{
cout"THERE?IS?NO?PATH."endl;
}

delete?[]quei;
delete?[]quej;
delete?[]prep;
}

C++的迷宫问题

#includeiostream
#includefstream
using namespace std;
struct DataType //定义描述迷宫中当前位置的结构类型
{
int x; //x代表当前位置的行坐标
int y; //y代表当前位置的列坐标
int pre; //pre表示移动到下一步的方向
};
struct Move //定义下一个位置的方向
{
int x;
int y;
};
struct LinkNode //链表结点
{
DataType data;
LinkNode *next;
};
//下面定义栈
class stack
{
private:
LinkNode *top; //指向第一个结点的栈顶指针
public:
stack(); //构造函数，置空栈
~stack(); //析构函数
void Push(DataType data); //把元素data压入栈中
DataType Pop(); //使栈顶元素出栈
DataType GetPop(); //取出栈顶元素
void Clear(); //把栈清空
bool IsEmpty(); //判断栈是否为空，如果为空则返回1，否则返回0
};

/////////////////////////////////////
/////////LinkList.cpp文件////////////
#include"LinkList.h"
stack::stack() //构造函数，置空栈
{
top=NULL;
}
stack::~stack() //析构函数
{
/* LinkNode *p=top;
while(top!=NULL)
{
p=top;
top=top-next;
// delete p;
}*/

}
void stack::Push(DataType x) //把元素data压入栈中
{
LinkNode *TempNode;
TempNode=new LinkNode;
TempNode-data=x;
TempNode-next=top;
top=TempNode;
}
DataType stack::Pop() //使栈顶元素出栈
{
DataType Temp;
LinkNode *TempNode;
//if(top==NULL) return NULL;
// else
// {
TempNode=top;
top=top-next;
Temp=TempNode-data;
delete TempNode;
return Temp;
// }
}
DataType stack::GetPop() //取出栈顶元素
{
return top-data;
}
void stack::Clear() //把栈清空
{
top=NULL;
}
bool stack::IsEmpty() //判断栈是否为空，如果为空则返回1，否则返回0
{
if(top==NULL) return true;
else return false;
}
////////////////////////////////////////////////////////
////////////////main.cpp文件////////////////////////////

#include"LinkList.h"
Move move[4]={{0,1},{1,0},{0,-1},{-1,0}}; //定义当前位置移动的4个方向
bool Mazepath(int **maze,int m,int n);
//寻找迷宫maze中从（0，0）到（m,n）的路径
//到则返回true,否则返回false
void PrintPath(stack p); //输出迷宫的路径
void Restore(int **maze,int m,int n); //恢复迷宫
int** GetMaze(int m,int n); //获取迷宫（可从文件中读取，也可输入）
//返回存取迷宫的二维指针

int main()
{
int m=0,n=0; //定义迷宫的长和宽
int **maze; //定义二维指针存取迷宫
maze=GetMaze(m,n); //调用GetMaze(int m,int n)函数，得到迷宫
if(Mazepath(maze,m,n)) //调用Mazepath(int **maze,int m,int n)函数获取路径
cout"迷宫路径探索成功!\n";
else cout"路径不存在!\n";
return 0;
}

int** GetMaze(int m,int n)
//获取迷宫（可从文件中读取，也可输入）
//返回存取迷宫的二维指针
{
int **maze; //定义二维指针存取迷宫
int i=0,j=0;
char Choose; //定义一个标志，选择读取文件或直接输入，获取迷宫
cout"请选择从文件中读取文件(1)或重新输入(2):";
cinChoose; //输入标志
if(Choose=='1') //当标志Choose为‘1’时，读取文件
{
cout"文件里的数字化迷宫如下:\n";
char ch; //定义一个字符，读取文件中的内容
i=0,j=0;
//首先得到文件中数字字符的数目，并得到迷宫的长和宽
ifstream fip("test.txt");
//定义一个文件对象，并打开文件“test.txt”
while(fip.get(ch)) //从读取文件中内容（一个个字符）
{
if(ch='0'ch='9') //获取文件中的数字字符
{
j++; //如果是字符，宽就加1
}
if(ch=='\n')
{
i++; //如果是换行，就行加1
n=j; //得到宽，即列数
j=0;
}
}
fip.close(); //读取文件结束
m=i; //得到长即行数
maze=new int *[m+2]; //申请长度等于行数加2的二级指针
for(i= 0;im+2;i++) //申请每个二维指针的空间
{
maze[i]=new int[n+2];
}
i=j=1;
ifstream fip2("test.txt");//重新读取文件，以得到内容
while(fip2.get(ch))
{
if(ch='0'ch='9')
{
maze[i][j]=ch-'0'; //把数字字符转化为数字，并存到指针里
coutmaze[i][j]" "; //在屏幕中显示迷宫
j++;
}
if(ch=='\n') //遇到换行，指针也相应换行
{
coutendl;
i++;
j=1;
}
}
fip2.close(); //读取结束
}

else //Choose=2 ,输入迷宫
{
cout"请输入迷宫的长和宽:";
int a,b;
cinab; //输入迷宫的长和宽
cout"请输入迷宫内容:\n";
m=a;
n=b; //m,n分别代表迷宫的行数和列数
maze=new int *[m+2]; //申请长度等于行数加2的二级指针
for(i= 0;im+2;i++) //申请每个二维指针的空间
{
maze[i]=new int[n+2];
}
for(i=1;i=m;i++) //输入迷宫的内容，1代表可通，0代表不通
for(j=1;j=n;j++)
cinmaze[i][j];
cout"是否保存新迷宫？\n";
char choose;
cinchoose;
if(choose=='Y'||choose=='y')
{
char ch;
ofstream fop("Newtest.txt");
for(i=1;i=m;i++)
{
for(j=1;j=n;j++)
{
ch='0'+maze[i][j];
fopch;
}
fopendl;
flush(cout);
}
fop.close();
}
}
//给迷宫的四周加一堵墙，即把迷宫四周定义为1
for(i=0;im+2;i++)
maze[i][0]=maze[i][n+1]=1;
for(i=0;in+2;i++)
maze[0][i]=maze[m+1][i]=1;
return maze; //返回存贮迷宫的二维指针maze
}
bool Mazepath(int **maze,int m,int n)
//寻找迷宫maze中从（0，0）到（m,n）的路径
//到则返回true,否则返回false
{
stack q,p; //定义栈p、q,分别存探索迷宫的过程和存储路径
DataType Temp1,Temp2;
int x,y,loop;
Temp1.x=1;
Temp1.y=1;
q.Push(Temp1); //将入口位置入栈
p.Push(Temp1);
maze[1][1]=-1; //标志入口位置已到达过
while(!q.IsEmpty()) //栈q非空，则反复探索
{
Temp2=q.GetPop(); //获取栈顶元素
if(!(p.GetPop().x==q.GetPop().xp.GetPop().y==q.GetPop().y))
p.Push(Temp2);
//如果有新位置入栈，则把上一个探索的位置存入栈p
for(loop=0;loop4;loop++) //探索当前位置的4个相邻位置
{
x=Temp2.x+move[loop].x; //计算出新位置x位置值
y=Temp2.y+move[loop].y; //计算出新位置y位置值
if(maze[x][y]==0) //判断新位置是否可达
{
Temp1.x=x;
Temp1.y=y;
maze[x][y]=-1; //标志新位置已到达过
q.Push(Temp1); //新位置入栈
}
if((x==(m))(y==(n))) //成功到达出口
{
Temp1.x=m;
Temp1.y=n;
Temp1.pre=0;
p.Push(Temp1); //把最后一个位置入栈
PrintPath(p); //输出路径
Restore(maze,m,n); //恢复路径
return 1; //表示成功找到路径
}
}
if(p.GetPop().x==q.GetPop().xp.GetPop().y==q.GetPop().y)
//如果没有新位置入栈，则返回到上一个位置
{
p.Pop();
q.Pop();
}
}
return 0; //表示查找失败，即迷宫无路经
}
void PrintPath(stack p) //输出路径
{
cout"迷宫的路径为\n";
cout"括号内的内容分别表示为(行坐标,列坐标,数字化方向,方向)\n";
stack t; //定义一个栈，按从入口到出口存取路径
int a,b;
DataType data;
LinkNode *temp;
temp=new LinkNode; //申请空间
temp-data=p.Pop(); //取栈p的顶点元素，即第一个位置
t.Push(temp-data); //第一个位置入栈t
delete temp; //释放空间
while(!p.IsEmpty()) //栈p非空，则反复转移
{
temp=new LinkNode;
temp-data=p.Pop(); //获取下一个位置
//得到行走方向
a=t.GetPop().x-temp-data.x; //行坐标方向
b=t.GetPop().y-temp-data.y; //列坐标方向
if(a==1) temp-data.pre=1; //方向向下，用1表示
else if(b==1) temp-data.pre=2; //方向向右，用2表示
else if(a==-1) temp-data.pre=3; //方向向上，用3表示
else if(b==-1) temp-data.pre=4; //方向向左，用4表示
t.Push(temp-data); //把新位置入栈
delete temp;
}
//输出路径，包括行坐标，列坐标，下一个位置方向
while(!t.IsEmpty()) //栈非空，继续输出
{
data=t.Pop();
cout'('data.x','data.y','data.pre","; //输出行坐标，列坐标
switch(data.pre) //输出相应的方向
{
case 1:cout"↓)\n";break;
case 2:cout"→)\n";break;
case 3:cout"↑)\n";break;
case 4:cout"←)\n";break;
case 0:cout")\n";break;
}
}
}
void Restore(int **maze,int m,int n) //恢复迷宫
{
int i,j;
for(i=0;im+2;i++) //遍历指针
for(j=0;jn+2;j++)
{
if(maze[i][j]==-1) //恢复探索过位置，即把-1恢复为0
maze[i][j]=0;
}
}
  • 随机文章
  • 梦幻西游普通副本必刷的六个,梦幻西游平顶山副本奖励怎么样
  • 穿越火线枪战王者717活动红包领不了怎么办_穿越火线新手福利在哪里领
  • 推荐几个PC手柄+键盘的双人游戏,双人手柄单机游戏
  • 三国志9替天行道：梁山实际上的二把手鲁智深，独占山头文武兼备
  • 永恒之塔35级任务,讨宾塔奇的欢心_永恒之塔35级副本
  • 丢失2个哨位，211高地仍打胜仗！廖锡龙：八条经验，实在可行
  • lol最新半人马符文天赋加点，混线和打野。好的加分。_人马打野天赋征服者是谁
  • 王者荣耀520皮肤介绍 520情侣皮肤是哪个英雄的
  • 跪求新世界韩国免费观看完整版，【免费高清】在线观看百度网盘资源,世界各家免费版安卓
  • 龙之谷十字军PK加点，求大神上图_龙之谷十字军加点技能图2023
  • DNF：变废为宝！自定义词条改版，不要冲动分解了
  • 我的世界铁矿最佳层数是多少_我的世界117铁矿最多在哪一层

    • 标签 跪求老鼠走迷宫游戏必须用c编写用栈来实现因为是数据结构课程设计所以只要现成代码越快越好_走迷宫编程怎么做

    版权声明：除非特别标注，否则均为本站原创文章，转载时请以链接形式注明文章出处。

    上一篇王者荣耀从哪个赛季开始_王者荣耀s18赛季什么时候结束的啊

    上一篇蓝龙岛的蓝龙岛攻略_蓝龙刷新位置

    相关文章