Question

找一个数据结构迷宫求解的程序？

Answer 1

#include <iostream>
#include <stack>
using namespace std;
enum direction {EAST = 0,NORTH,WEST,SOUTH};
const int WALL = 1;
const int ROAD = 0;
struct PosType {
int x;
int y;
bool operator==(const PosType &rhs) {
return x == rhs.x && y == rhs.y;
}
bool operator!=(const PosType &rhs) {
return !operator==(rhs);
}
};
struct SElemType {
int ord;
int di;
PosType pos;
PosType prepos;
};
PosType NextPos(PosType curpos,int nd) {
switch(nd) {
case 1:
curpos.x++;
break;
case 2:
curpos.y--;
break;
case 3:
curpos.x--;
break;
case 4:
curpos.y++;
break;
default:
break;
}
return curpos;
}
void MazePath(stack<SElemType> &S,const int maze[][10],PosType start,PosType end) {

SElemType et;
PosType curpos = start;
{
et.di = -1;
et.pos.x = 1000;
et.pos.y = 1000;
et.prepos.x = 1000;
et.prepos.y = 1000;
et.ord = 0;
}
S.push(et);

int curstep = 1;
do {
if(curpos != S.top().prepos && maze[curpos.y][curpos.x] != WALL) {
{
et.ord = curstep;
et.pos = curpos;
et.prepos = S.top().pos;
}
S.top().di = et.di;
S.push(et);
et.di = 1;
if(curpos == end) return;
curpos = NextPos(curpos,et.di);
curstep++;
}
else {
if(!S.empty()) {
while(et.di == 4 && !S.empty()) {
curpos = S.top().pos;
S.pop();
et = S.top();
}
if(et.di < 4) {
curpos = NextPos(et.pos,++et.di);
}
}
}
}while(!S.empty());
return;
}

int main() {
int map[][10] = {
{1,1,1,0,1,1,1,1,1,1},
{1,1,1,0,1,1,1,1,1,1},
{1,1,1,0,1,1,1,1,1,1},
{1,1,1,0,0,0,1,1,1,1},
{1,1,1,0,1,0,1,1,1,1},
{1,1,0,0,1,1,1,1,1,1},
{1,1,0,1,1,1,1,1,1,1},
{1,1,0,0,1,1,1,1,1,1},
{1,1,1,0,1,1,1,1,1,1},
{1,1,1,0,1,1,1,1,1,1},
};
stack<SElemType> S;
PosType start = {3,8},end = {3,0};

MazePath(S,map,start,end);

for(int i = 0,j = S.size();i < j - 1;++i) {
cout << S.top().pos.x << " " << S.top().pos.y << " " << S.top().di << endl;
S.pop();
}

return 0;
}

Answer 2

文件hsdy.h
#define I 100
#define J 100struct Maze
{
int x;
int y;
struct Maze *next;
}maze;int zb[I][J];
int n,m;
int xi,yj;
struct Maze *head,*start,*end;
int way=2;//方向初始化为下 0上 1左 2下 3右void Initialization();
void move();
int move_pd();
int fx_xz();
int fx_pd(int way_fx);
int f(int way);
void in();
void out();
void way_zb();
void output();主文件
#include <stdio.h>
#include <malloc.h>
#include "hsdy2.h"int main()
{
Initialization();
move();
output2();
return 0;
}void Initialization()//初始化
{
int i,j;
scanf("%d%d",&n,&m);
for(i=0;i<n;i++)
for (j=0;j<m;j++)
scanf("%d",&zb[i][j]);
start=(struct Maze*)malloc(sizeof(struct Maze));
head=(struct Maze*)malloc(sizeof(struct Maze));
start->next=head;
head->x=head->y=1;head->next=NULL;
}void move()//移动
{
while(head->x!=n-2 || head->y!=m-2)
{
move_pd();
}
}int move_pd()//移动判断
{
int pd;
pd=fx_xz();
if(pd<0){
zb[head->x][head->y]=2;//把去过的行不通的地方赋值为2
out();//出栈
}
else{
way=pd;
in();//进栈

}
return 0;
}int fx_xz()//方向选择 返回新的方向
{
if(fx_pd((f(way)+1)%4)==1) return (f(way)+1)%4;
else if(fx_pd(way)==1) return way;
else if(fx_pd((way+1)%4)==1) return (way+1)%4;
else return -1;
}int fx_pd(int way_fx)
{
xi=head->x;yj=head->y;
switch(way_fx){
case 0:xi--;break;
case 1:yj--;break;
case 2:xi++;break;
case 3:yj++;break;
}
if(zb[xi][yj]==0) return 1;
return 0;
}int f(int way)//取反方向
{
switch(way){
case 0:return 2;
case 1:return 3;
case 2:return 0;
case 3:return 1;
}
return 0;
}void in()//进栈
{
struct Maze *p;
if((p=(struct Maze*)malloc(sizeof(struct Maze)))==NULL)
printf("内存分配错误！");
else{
p->next=head;
start->next=p;
head=p;
way_zb();//赋予该位置坐标
}
}void out()//出栈
{
head=head->next;
start->next=head;
}void way_zb()//结点坐标赋值
{
head->x=head->next->x;
head->y=head->next->y; switch(way){
case 0:head->x--;break;
case 1:head->y--;break;
case 2:head->x++;break;
case 3:head->y++;break;
}
}void output()
{
struct Maze *p;
p=start->next;
while(p!=NULL){
printf("%d %d\n",p->x,p->y);
p=p->next;
}
}