走迷宫问题？
写的程序在迷宫有同路时过5秒钟才有结果，在迷宫无同路时，电脑死机，内存狂吃到97%
谁能告诉我好的结果和算法啊。
大家可以只看main函数，或不可代码，给我思路就行。
我的思路是从入口开始，向下走不通就向右走，向右走不通就向上走，向上走不通就向左走
#include<iostream>
#include<stdlib.h>
#include"stack.h"
#include"map.h"
using namespace std;
int main()
{
map m;
stack path;
point p;
int i=m.i+2,j=m.j+2; //地图大小
p.x=1;p.y=1;
path.push_back(p);
while((p.x!=8)||(p.y!=8)){
int dir=4;
if(m.point[(p.x+1)*j+p.y]==1)dir-=1;
if(m.point[(p.x)*j+p.y+1]==1)dir-=1;
if(m.point[(p.x-1)*j+p.y]==1)dir-=1;
if(m.point[(p.x)*j+p.y-1]==1)dir-=1;
if(dir==1)
{
point tem;
m.Setunable(p.x,p.y);
path.pop_back(tem);
p.x=path.top->num.x;
p.y=path.top->num.y;
continue;
}
if(dir==0){std::cout<<"此迷宫无通路";return 0;}
if(m.point[(p.x+1)*j+p.y]!=1) //先下走
{
p.x+=1;path.push_back(p);
}
else if(m.point[(p.x)*j+p.y+1]!=1) //向右走
{
p.y+=1;path.push_back(p);
}
else if(m.point[(p.x-1)*j+p.y]!=1) //向上走
{
p.x-=1;path.push_back(p);
}
else if(m.point[(p.x)*j+p.y-1]!=1) //向左走
{
p.y-=1;path.push_back(p);
}
else;
}
//接下来输出路径，因为栈是后进先出，所以新建一个栈保路径，确保输出顺序
std::cout<<"\n走过的路径为："<<std::endl;
point tem;
stack path2;
while(!path.Isempty()){
path.pop_back(tem);
path2.push_back(tem);
}
path2.traversing();
std::cout<<endl;
return 0;
}
下面是：map.h文件
#include<fstream.h>
class map{
public:
int *point;
int i,j; //地图的大小
map();
void Setunable(int x,int y); //设置该点为“墙体”
};
map::map()
{
ifstream fileInput("map.txt");
if(fileInput.is_open())
{
fileInput>>i>>j;
point=new int[(i+2)*(j+2)];
int *p=point;
for(int i=0;i<=(i+2)*(j+2);i++)
{
fileInput>>*p;
p++;
}
}
}
void map::Setunable(int x,int y)
{
point[x*(j+2)+y]=1;
}
再是stack.h文件
typedef struct{
int x;
int y;
}point;
typedef struct Node{
point num;
struct Node *pNext;
}Node;
class stack{
public:
Node node;
Node*top;
stack();
void push_back(point a);
void pop_back(point &e);
bool Isempty();
void traversing();
};
stack::stack()
{
top=NULL;
}
void stack::push_back(point a)
{
Node*p;
p=new Node;
p->num.x=a.x;
p->num.y=a.y;
p->pNext=top;
top=p;
}
void stack::pop_back(point &e)
{
Node*p=top;
e.x=top->num.x;
e.y=top->num.y;
top=top->pNext;
delete p;
}
bool stack::Isempty()
{
return top==NULL;
}
void stack::traversing()
{
Node*p=top;
while(p){
std::cout<<"("<<p->num.x<<", "<<p->num.y<<") ";
p=p->pNext;
}
}
[解决办法]
可以试试遗传算法！！
[解决办法]
#include <stdio.h>
#include <stdlib.h>
#include <graphics.h>
#include <conio.h>
#include <dos.h>
#define COL 20
#define ROW 20
#define LEFT 120
#define TOP 40
#define RIGHT 520
#define BOTTOM 440
#define SMALL 20
int Maze[COL][ROW]={
{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1},
{1,0,0,1,0,0,1,0,0,0,1,0,0,0,0,0,1,1,1,1},
{1,0,1,0,0,1,0,0,1,0,1,0,1,1,0,1,0,0,0,1},
{1,0,1,0,1,1,0,1,1,0,1,0,1,0,0,1,0,1,0,1},
{1,0,0,0,0,1,0,0,1,0,0,0,1,0,1,1,0,1,0,1},
{1,1,1,0,1,1,1,0,1,1,1,1,0,0,1,0,0,1,0,1},
{1,1,0,0,1,1,0,0,1,0,0,1,0,1,1,0,1,0,0,1},
{1,0,0,1,1,0,0,1,0,0,1,0,0,1,0,0,1,0,1,1},
{1,0,1,1,0,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1},
{1,0,1,0,0,1,1,0,0,1,0,0,1,1,0,0,1,0,1,1},
{1,0,0,0,1,1,0,1,0,0,0,1,1,0,1,0,1,0,0,1},
{1,0,1,1,1,0,0,1,1,1,0,1,1,0,1,0,1,1,0,1},
{1,0,0,1,0,0,1,0,1,0,0,1,0,0,0,0,1,0,0,1},
{1,1,0,1,1,0,1,0,0,1,0,1,1,1,0,1,1,0,1,1},
{1,0,0,0,1,0,1,1,0,1,0,1,0,0,0,1,0,0,0,1},
{1,0,1,0,1,0,0,0,0,1,0,0,0,1,1,0,0,1,0,1},
{1,0,1,0,1,0,1,1,0,0,1,0,1,1,0,0,1,1,0,1},
{1,0,1,1,0,0,0,0,1,0,1,1,0,0,1,0,0,0,1,1},
{1,0,0,0,0,1,0,1,1,0,0,0,0,1,1,0,1,0,0,1},
{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}};
int flag=1;
typedef struct Seat
{
int x,y;
int dir;
}Seat;
typedef struct LSNode
{
Seat data;
struct LSNode* next;
}LSNode,*SNode;
typedef struct LSk
{
SNode top;
}LSk,*LStack;
void InitLStack(LStack LS)
{
if(LS==NULL)
{
LS=(LStack)malloc(sizeof(LSk));
}
LS->top=NULL;
}
Seat* Peek(LStack LS)
{
Seat* p;
Seat temp;
temp=LS->top->data;
p=(Seat*)malloc(sizeof(Seat));
p->dir=temp.x;
p->x=temp.x;
p->y=temp.y;
return p;
}
void Push(LStack LS,Seat value)
{
SNode p;
p=(SNode)malloc(sizeof(LSNode));
p->data.x=value.x;
p->data.y=value.y;
p->data.dir=value.dir;
p->next=LS->top;
LS->top=p;
}
Seat* Pop(LStack LS)
{
SNode p;
Seat *res;
Seat temp;
res=(Seat*)malloc(sizeof(Seat));
res->x=-1;
res->y=-1;
res->dir=0;
p=LS->top;
if(p==NULL)
{
flag=0;
return res;
}
temp=p->data;
res->x=temp.x;
res->y=temp.y;
res->dir=temp.dir;
LS->top=p->next;
return res;
}
int IsEmpty(LStack LS)
{
if(LS->top==NULL)
return 1;
else
return 0;
}
void Print(LStack LS)
{
SNode p;
if(LS->top==NULL)
{
printf("No path\n");
return;
}
p=LS->top;
printf("Path is as follow:\n");
while(p!=NULL)
{
printf("%d,%d\t",p->data.x,p->data.y);
p=p->next;
}
printf("\n");
}
void drawcake(int x,int y)
{
setfillstyle(SOLID_FILL,BLUE);
bar(LEFT+1+x*SMALL,TOP+1+y*SMALL,RIGHT-1-19*SMALL+x*SMALL,BOTTOM-1-19*SMALL+y*SMALL);
}
void draw(int x,int y)
{
setfillstyle(SOLID_FILL,RED);
bar(LEFT+5+x*SMALL,TOP+5+y*SMALL,RIGHT-5-19*SMALL+x*SMALL,BOTTOM-5-19*SMALL+y*SMALL);
}
void undraw(int x,int y)
{
setfillstyle(SOLID_FILL,BLACK);
bar(LEFT+5+x*SMALL,TOP+5+y*SMALL,RIGHT-5-19*SMALL+x*SMALL,BOTTOM-5-19*SMALL+y*SMALL);
}
void footprint(int x,int y)
{
setfillstyle(SOLID_FILL,GREEN);
bar(LEFT+5+x*SMALL,TOP+5+y*SMALL,RIGHT-5-19*SMALL+x*SMALL,BOTTOM-5-19*SMALL+y*SMALL);
}
void Tranverse(Seat start,Seat end,LStack LS)
{
Seat cur;
Seat *top;
start.dir=1;
Push(LS,start);
top=Peek(LS);
while(!IsEmpty(LS)&&(top->x!=end.x||top->y!=end.y))
{
top=Pop(LS);
cur.x=top->x;
cur.y=top->y;
cur.dir=top->dir;
if(cur.dir==5)
{
Maze[cur.x][cur.y]=0;
footprint(cur.y,cur.x);
continue;
}
else
{
switch(cur.dir)
{
case 1:
if(cur.y+1<COL)
{
if(Maze[cur.x][cur.y+1]==0)
{
Maze[cur.x][cur.y+1]=2;
cur.dir=2;
Push(LS,cur);
cur.dir=1;
cur.y+=1;
Push(LS,cur);
draw(cur.y,cur.x);
break;
}
}
cur.dir=2;
Push(LS,cur);
break;
case 2:
if(cur.x+1<ROW)
{
if(Maze[cur.x+1][cur.y]==0)
{
Maze[cur.x+1][cur.y]=2;
cur.dir=3;
Push(LS,cur);
cur.dir=1;
cur.x+=1;
Push(LS,cur);
draw(cur.y,cur.x);
break;
}
}
cur.dir=3;
Push(LS,cur);
break;
case 3:
if(cur.y-1>=0)
{
if(Maze[cur.x][cur.y-1]==0)
{
Maze[cur.x][cur.y-1]=2;
cur.dir=4;
Push(LS,cur);
cur.dir=1;
cur.y-=1;
Push(LS,cur);
draw(cur.y,cur.x);
break;
}
}
cur.dir=4;
Push(LS,cur);
break;
case 4:
if(cur.x-1>=0)
{
if(Maze[cur.x-1][cur.y]==0)
{
Maze[cur.x-1][cur.y]=2;
cur.dir=5;
Push(LS,cur);
cur.dir=1;
cur.x-=1;
Push(LS,cur);
draw(cur.y,cur.x);
break;
}
}
cur.dir=5;
Push(LS,cur);
break;
}
}
top=Peek(LS);
delay(20000);
}
getch();
}
void Human()
{
char ch;
int x=1,y=1;
do{
ch=bioskey(0);
switch(ch)
{
case 19200:
if(Maze[y][x-1]==0)
{
undraw(x,y);
Maze[y][x]=0;
x--;
draw(x,y);
Maze[y][x]=2;
}
break;
case 19712:
if(Maze[y][x+1]==0)
{
undraw(x,y);
Maze[y][x]=0;
x++;
draw(x,y);
Maze[y][x]=2;
}
break;
case 18432:
if(Maze[y-1][x]==0)
{
undraw(x,y);
Maze[y][x]=0;
y--;
draw(x,y);
Maze[y][x]=2;
}
break;
case 20480:
if(Maze[y+1][x]==0)
{
undraw(x,y);
Maze[y][x]=0;
y++;
draw(x,y);
Maze[y][x]=2;
}
break;
}
if(Maze[18][18]==2)ch=283;
}while(ch!=283);
if(Maze[18][18]==2)printf(" You are successed !");
getch();
}
int main()
{
LStack ls;
Seat st;
Seat en;
int gr=DETECT,gm,i,j,x=1,y=1,ch;
float f;
st.x=1; st.y=1; st.dir=1;
en.x=18;en.y=18;en.dir=1;
ls=(LStack)malloc(sizeof(LSk));
InitLStack(ls);
registerbgidriver(EGAVGA_driver);
initgraph(&gr,&gm,"");
cleardevice();
getch();
setbkcolor(0);
for(i=0;i<20;i++)
for(j=0;j<20;j++)
if(Maze[i][j]==1)drawcake(j,i);
draw(x,y);
printf("Tranverse start:\n");
Tranverse(st,en,ls);
getch();
return 0;
}
[解决办法]
最近刚写了迷宫问题 用了两个算法 一个用递归调用 另个一非递归算法 还有迷宫无路时 你可以再加一个数组进行标记已经探测的位置
[解决办法]
记得高级人工智能有迷宫的算法
