📄 复件 maze.cpp
字号:
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#define MAXNUM 8
//定义坐标位置类型
typedef struct PositionType{
int row;
int col;
int nextDirection;
//0表示障碍，1表示通路，2表示开始点，3表示结束点，*表示走过的路径，@表示死路，#表示碰到的障碍
char sign;
}PositionType;
typedef PositionType SElemType;
typedef struct LNode
{
SElemType data;
struct LNode *next;
}LNode,*LinkStack;
int initStack(LinkStack &S)
{
S=new LNode;
S->next=NULL;
return 1;
}
int stackLength(LinkStack S)
{
LinkStack p;
p=new LNode;
int i=0;
p=S->next;
while(p)
{
i++;
p=p->next;
}
return i;
}
int pop(LinkStack &S,SElemType &e)
{
if(S->next!=NULL)
{
e=S->next->data;
S->next=S->next->next;
return 1;
}
else return 0;
}
int clearStack(LinkStack &S)
{
LinkStack p;
p=new LNode;
while(S->next)
{
p=S->next;
S->next=S->next->next;
delete p;
}
return 1;
}
int getTop(LinkStack &S,SElemType &e)
{
LinkStack p=new LNode;
p=S->next;
e=p->data;
return 1;
}
int push(LinkStack &S,SElemType e)
{
LinkStack p;
p=new LNode;
p->data=e;
p->next=S->next;
S->next=p;
return 1;
}
int destroyStack(LinkStack &S)
{
LinkStack q;
while(S)
{
q=S->next;
delete S;
S=q;
}
return 1;
}
int stackEmpty(LinkStack &S)
{
LinkStack p=S;
if(p->next)
return 0;
else return 1;
}
//找到开始位置
PositionType findBegin(PositionType pos[MAXNUM][MAXNUM]){
int i,j;
for(i=0;i<MAXNUM;i++){
for(j=0;j<MAXNUM;j++){
if(pos[i][j].sign=='2'){
break;
}
}
if(pos[i][j].sign=='2') break;
}
//printf("开始节点是第%d行，%d列%c",i,j,pos[i][j].sign);
if(i<MAXNUM&&j<MAXNUM){
return pos[i][j];
}
return pos[0][0];
};
//找到结尾
PositionType findEnd(PositionType pos[MAXNUM][MAXNUM]){
int i,j;
for(i=0;i<MAXNUM;i++){
for(j=0;j<MAXNUM;j++){
if(pos[i][j].sign=='3'){
break;
}
}
if(pos[i][j].sign=='3') break;
}
if(i<MAXNUM&&j<MAXNUM){
return pos[i][j];
}
return pos[MAXNUM-1][MAXNUM-1];
};
void printSign(PositionType pos[MAXNUM][MAXNUM],PositionType * current,char a){
pos[current->row][current->col].sign=a;
}
//找到下一个位置
PositionType * findNextPosition(PositionType * current,PositionType pos[MAXNUM][MAXNUM],LinkStack &S){
PositionType pt;
while(1){
if(current->nextDirection==5){
//if(stackEmpty(S)==0){
printSign(pos,current,'@');
pop(S,pt);
//pop(S,pt);
//pop(S,pt);
current=&pos[pt.row][pt.col];
printf("%d,%d\n",current->row,current->col);
//current=findNextPosition(current,pos,S);
return current;
//} else{
// return &pos[MAXNUM-1][MAXNUM-1];
//}
}
if(current->nextDirection==1){
pos[current->row][current->col].nextDirection++;
if(pos[current->row][current->col+1].sign=='0'||pos[current->row][current->col+1].sign=='1'||pos[current->row][current->col+1].sign=='3'){
current=&pos[current->row][current->col+1];
return current;
}
//break;
}
if(current->nextDirection==2){
pos[current->row][current->col].nextDirection++;
if(pos[current->row-1][current->col].sign=='0'||pos[current->row-1][current->col].sign=='1'||pos[current->row-1][current->col].sign=='3'){
current=&pos[current->row-1][current->col];
return current;
}
//break;
}
if(current->nextDirection==3){
pos[current->row][current->col].nextDirection++;
if(pos[current->row][current->col-1].sign=='0'||pos[current->row][current->col-1].sign=='1'||pos[current->row-1][current->col].sign=='3'){
current=&pos[current->row][current->col-1];
return current;
}
//break;
}
if(current->nextDirection==4){
pos[current->row][current->col].nextDirection++;
if(pos[current->row+1][current->col].sign=='0'||pos[current->row+1][current->col].sign=='1'||pos[current->row+1][current->col].sign=='3'){
current=&pos[current->row+1][current->col];
return current;
}
if(pos[current->row+1][current->col].sign=='@'||pos[current->row+1][current->col].sign=='#'){
pop(S,pt);
}
//break;
}
}
}
void print(PositionType pos[MAXNUM][MAXNUM],LinkStack &S){
int i,j;
for(i=0;i<MAXNUM;i++){
for(j=0;j<MAXNUM;j++){
if(pos[i][j].sign=='*'){
//textcolor(RED);
switch(pos[i][j].nextDirection){
case 1:
case 2:
printf("→");
break;
case 3:
printf("↑");
break;
case 4:
printf("←");
break;
case 5:
printf("↓");
break;
}
}else
printf("%c ",pos[i][j].sign);
}
printf("\n");
}
}
//返回类型为整形，0表示找不到起点，1表示找不到终点，2表示找到路径，3表示找不到路径
int mazePath(PositionType pos[MAXNUM][MAXNUM],LinkStack &S){
//LinkStack S;
PositionType begin;
PositionType end;
PositionType pt;
PositionType * current;
PositionType * point;
begin=findBegin(pos);
if(begin.row==0&&begin.col==0){
return 0;
}
end=findEnd(pos);
if(end.row==MAXNUM-1&&end.col==MAXNUM-1){
return 1;
}
current=&begin;//初始时指向开始位置
//printf("%c",current->sign);
int allStep=0;
initStack(S);
//主循环体
do{
switch(current->sign){
case '1':
case '2':
point=current;
current=findNextPosition(&pos[current->row][current->col],pos,S); //找到下一个节点
printSign(pos,point,'*');
push(S, pos[point->row][point->col]);
break;
case '3':
printf("当前的符号是%c,当前元素在第%d行，第%d列, nextDirection的值是%d\n",current->sign,current->row,current->col,current->nextDirection);
push(S,pos[current->row][current->col]);
break;
case '0':
printSign(pos,&pos[current->row][current->col],'#');
pop(S,pt);
current=&pos[pt.row][pt.col];
break;
case '*':
if(current->nextDirection!=5){
push(S, *current);
}
current=findNextPosition(&pos[current->row][current->col],pos,S); //找到下一个节点
break;
}
allStep++;
/*printf("第%d次循环\n",allStep);
printf("第1行第4列的nextDirection值是%d\n",pos[1][4].nextDirection);
getTop(S,pt);
printf("当前栈的高度是%d\n",stackLength(S));
printf("栈顶的符号是%c,栈顶元素在第%d行，第%d列，nextDirection的值是%d\n",pos[pt.row][pt.col].sign,pos[pt.row][pt.col].row,pos[pt.row][pt.col].col,pos[pt.row][pt.col].nextDirection);
printf("当前的符号是%c,当前元素在第%d行，第%d列, nextDirection的值是%d\n",current->sign,current->row,current->col,current->nextDirection);
print(pos);*/
} while(stackEmpty(S)==0 && pos[current->row][current->col].sign!='3');
if(stackLength(S)!=0){
printf("该迷宫所走的路径数为%d,共循环了%d次。\n",stackLength(S),allStep);
getTop(S,pt);
printf("栈顶的符号是%c,栈顶元素在第%d行，第%d列，nextDirection的值是%d\n",pos[pt.row][pt.col].sign,pos[pt.row][pt.col].row,pos[pt.row][pt.col].col,pos[pt.row][pt.col].nextDirection);
//printf("%d",stackLength(S));
return 2;
} else{
printf("该迷宫不存在通路！");
return 3;
}
destroyStack(S);
}
//返回另外一条通路，1表示迷宫不存在通路，2表示还有其他通路
int findAnotherPath(PositionType pos[MAXNUM][MAXNUM],LinkStack &S){
PositionType pt;
int allStep=0;
PositionType * current;
PositionType * point;
//pop(S,pt);
pop(S,pt);
current=&pos[pt.row][pt.col];
do{
switch(current->sign){
case '1':
case '2':
point=current;
current=findNextPosition(&pos[current->row][current->col],pos,S); //找到下一个节点
printSign(pos,point,'*');
push(S, pos[point->row][point->col]);
break;
case '3':
printf("当前的符号是%c,当前元素在第%d行，第%d列, nextDirection的值是%d\n",current->sign,current->row,current->col,current->nextDirection);
push(S,pos[current->row][current->col]);
break;
case '0':
printSign(pos,&pos[current->row][current->col],'#');
pop(S,pt);
current=&pos[pt.row][pt.col];
break;
case '*':
if(current->nextDirection!=5){
push(S, *current);
}
current=findNextPosition(&pos[current->row][current->col],pos,S); //找到下一个节点
break;
}
allStep++;
//printf("查找其他路径的第%d次循环\n",allStep);
//printf("第1行第4列的nextDirection值是%d\n",pos[1][4].nextDirection);
//getTop(S,pt);
//printf("当前栈的高度是%d\n",stackLength(S));
//printf("栈顶的符号是%c,栈顶元素在第%d行，第%d列，nextDirection的值是%d\n",pos[pt.row][pt.col].sign,pos[pt.row][pt.col].row,pos[pt.row][pt.col].col,pos[pt.row][pt.col].nextDirection);
//printf("当前的符号是%c,当前元素在第%d行，第%d列, nextDirection的值是%d\n",current->sign,current->row,current->col,current->nextDirection);
//print(pos,S);
} while(stackEmpty(S)==0 && pos[current->row][current->col].sign!='3');
if(stackEmpty(S)==1){
return 1;
}
if(pos[current->row][current->col].sign=='3'){
printf("该迷宫还有其他通路！");
return 2;
}
}
int findOtherPathes(PositionType pos[MAXNUM][MAXNUM],LinkStack &S){
int state=2;
int pathNumber=-1;
printf("该迷宫的其他通路");
while(state==2){
pathNumber++;
state=findAnotherPath(pos,S);
//printf("该迷宫的其他通路");
print(pos,S);
}
return pathNumber;
}
void head(){
int i,j;
for(i=0;i<25;i++){
printf(" *");
}
printf("\n 请输入字母来完成选择您要执行的操作........\n\n");
printf(" 输入c迷宫将按照默认的方式创建\n");
printf(" 输入n可查看当前迷宫共有多少条路径\n");
printf(" 输入f后系统将按照您指定的文件来创建迷宫\n");
printf(" 输入l将可以看到系统给您找到的默认路径\n");
printf(" 输入a将可以看到所有迷宫路径\n");
printf(" 输入h将看到帮助信息");
printf(" 输入q将推出系统\n");
for(i=0;i<25;i++){
printf(" *");
}
printf("\n\n\n");
}
//如果能匹配返回1
int match(char command){
switch(command){
case 'c':
return 1;
case 'n':
return 1;
case 'f':
return 1;
case 'l':
return 1;
case 'a':
return 1;
case 'h':
return 1;
case 'q':
return 1;
}
return 0;
}
void Control(){
char command;
PositionType pos[MAXNUM][MAXNUM];
LinkStack S;
do{
gets(command);
switch(command){
case 'c':
char array[MAXNUM][MAXNUM]={
{'0','0','0','0','0','0'},
{'0','2','1','1','1','0'},
{'0','1','1','0','1','0'},
{'0','1','1','1','3','0'},
{'0','0','0','0','0','0'}
};
//使迷宫初始化
for(i=0;i<MAXNUM;i++){
for(j=0;j<MAXNUM;j++){
pos[i][j].row=i;
pos[i][j].col=j;
pos[i][j].nextDirection=1;
pos[i][j].sign=array[i][j];
}
}
state=mazePath(pos,S);
if(state==0){
printf("找不到开始节点，请重新输入迷宫！");
}
if(state==1){
printf("找不到终点，请重新输入迷宫！");
}
if(state==2){
print(pos,S);
pathNumber=findOtherPathes(pos,S);
}
if(state==3){
printf("该迷宫没有通路！");
}
printf("该迷宫共有%d条通路\n",++pathNumber);
//使迷宫初始化
for(i=0;i<MAXNUM;i++){
for(j=0;j<MAXNUM;j++){
pos[i][j].row=i;
pos[i][j].col=j;
pos[i][j].nextDirection=1;
pos[i][j].sign=array[i][j];
}
}
}
} while(!match(command));
}
void main(){
//PositionType pos[MAXNUM][MAXNUM];
int i,j,state,pathNumber=0;
//LinkStack S;
readCommand();
char array[MAXNUM][MAXNUM]={
{'0','0','0','0','0','0'},
{'0','2','1','1','1','0'},
{'0','1','1','0','1','0'},
{'0','1','1','1','3','0'},
{'0','0','0','0','0','0'}
};
//使迷宫初始化
for(i=0;i<MAXNUM;i++){
for(j=0;j<MAXNUM;j++){
pos[i][j].row=i;
pos[i][j].col=j;
pos[i][j].nextDirection=1;
pos[i][j].sign=array[i][j];
}
}
state=mazePath(pos,S);
if(state==0){
printf("找不到开始节点，请重新输入迷宫！");
}
if(state==1){
printf("找不到终点，请重新输入迷宫！");
}
if(state==2){
print(pos,S);
pathNumber=findOtherPathes(pos,S);
/*while(anotherState==2){
pathNumber++;
anotherState=findAnotherPath(pos,S);
printf("该迷宫的其他通路");
print(pos,S);
}*/
}
if(state==3){
printf("该迷宫没有通路！");
}
printf("该迷宫共有%d条通路\n",++pathNumber);
system("pause");
}⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -