maze.cpp

编制一个求解迷宫通路的程序,1,0表示通路与不通

#include "stdio.h"
#include "stdlib.h"
typedef struct{
	int r,c;
	}PosType;   //路径位置，存储行和列值
typedef struct stack{
	 PosType seat;
	 int di;
	 struct stack *next,*prior;
 }Stack;   //栈类型，存放路径位置和下一路径方向
 typedef struct {
 	int m,n;  
 	char arr[20][20];
 	}MazeType;   //迷宫数据类型
void creatmaze(MazeType *p)
{   //创建迷宫
	int i,j;
	char filename[10];
	FILE *fp;
	printf("请输入迷宫数据所在文件名:");
	scanf("%s",filename);
	if((fp=fopen(filename,"r"))==NULL)
	{printf("无法打开文件");
	exit(0);}
	p->m=fgetc(fp)-48;
	p->n=fgetc(fp)-48;
	for(i=0;i<20;i++)
		for(j=0;j<20;j++)
			p->arr[i][j]='1';  
	for(i=1;i<=p->m;i++)
		for(j=1;j<=p->n;j++)
			p->arr[i][j]=fgetc(fp);  
}
void printmaze(MazeType *p)
{   //打印迷宫数据
	int i,j;
	printf("迷宫行数和列数为 :\n");
	printf("%d,%d\n",p->m,p->n);
	printf("迷宫数据为:\n");
	for(i=1;i<=p->m;i++)
	{for(j=1;j<=p->n;j++)
			printf("%c ",p->arr[i][j]);
	        printf("\n");
	}
}
int search(char ch[20][20] ,int x,int y)
{   //探索下一路径方向
       	if(ch[x][y+1]=='0') return(1);
       	else if(ch[x+1][y]=='0') return(2);
       	   else if(ch[x][y-1]=='0') return(3);
             else	if(ch[x-1][y]=='0') return(4);
                  	else return(5);
}
void mazepath(MazeType *p)
{   //寻找路径
	int i,j,k,l,dir;
	Stack *head,*q;
	printf("请输入入口位置(，隔开):");
	scanf("%d,%d",&i,&j);
	printf("请输入出口位置(，隔开):");
	scanf("%d,%d",&k,&l);
	head=(Stack *)malloc(sizeof(Stack));
	q=(Stack *)malloc(sizeof(Stack));
	head->next=q;
	q->prior=head;
	q->next=NULL;
	q->seat.r=i;
	q->seat.c=j;
	for(;!((i==k&&j==l)||(q==head));)
	{dir=search(p->arr,i,j);
	if(dir<=4){q->di=dir;
			   p->arr[i][j]='*';
			   q->next=(Stack *)malloc(sizeof(Stack));
			   q->next->prior=q;
			   q=q->next;
			   q->next=NULL;
			   if(dir==1) j++;
			   else if(dir==2) i++;
			     else if(dir==3) j--;
			        else i--;
			   q->seat.r=i;
			   q->seat.c=j;}
	else {q=q->prior;
	      free(q->next);
		  q->next=NULL;
		  p->arr[i][j]='#';
		  i=q->seat.r;
		  j=q->seat.c;}
	}
	if(i==k&&j==l)
	{printf("通路为:\n");
	 for(q=head->next,i=1;q->next!=NULL;q=q->next,i++)
	 {printf("(%d,%d,%d) ",q->seat.r,q->seat.c,q->di);
	 if(i%5==0) printf("\n");}
	 printf("(%d,%d)\n",k,l);
	}
	else printf("此迷宫从入口到出口没有路径\n");
}
void main()
{MazeType maze,*p;
p=&maze;
 creatmaze(p);
 printmaze(p);
 mazepath(p);
}