stroll_maze.cpp

本程序采用C开发

/* ==================== Program Description ====================== */
/* Program Title: Maze                                             */
/* Program Purpose: Find a nearest path.                           */
/* Written By: Gui Ripei -->                                       */
/*   HuBei Polytechnic University,Computer Science And Technology. */
/* Academic Advisor: Zhang Shengli                                 */
/* Date: 2004.9.23                                                 */
/*================================================================ */
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#define MAXVER 100
#define NULL 0

struct maze_matrix
{
	int maze[10][10];
    int rownum;
    int colnum;
};

struct listnode
{
	int adjno;
    struct listnode *next;
};

struct headnode
{
	int data;
	struct listnode *first;
};


struct algraph
{
	struct headnode adj[MAXVER];
    int vexnum;
};
typedef struct algraph ADJLIST;

typedef int List[MAXVER];
List visited,queue;
int *point[MAXVER];
output_line();

struct maze_matrix Input_matrix(int *p1,int *p2)
{int i,j,m,n,a,b,c,d;
 struct maze_matrix A;
 printf("\n\n\n\n\n");
 printf("                              WELCOME\n");
 printf("\n");
 printf("** Please input the amounts of the Row and the Column(Example -->n,n):");
 scanf("%d,%d",&i,&j);
 A.rownum=i;
 A.colnum=j;
 for(m=1;m<=i;m++)
        for(n=1;n<=j;n++)
        {
	    printf("** Please input %d row,the %d col ver(1 or 0):",m,n);
            scanf("%d",&A.maze[m-1][n-1]);
            if(A.maze[m-1][n-1]!=0&&A.maze[m-1][n-1]!=1)
            {
		printf("** Error!Please input again!\n");
		printf("\n");
                n--;
            }
        }
    printf("** Please input the Entry coordinate(Example -->n,n):");
    scanf("%d,%d",&a,&b);
    printf("** Please input the Exit coordinate(Example -->n,n):");
    scanf("%d,%d",&c,&d);
    *p1=(a-1)*j+b;
    *p2=(c-1)*j+d;
    return (A);
}

int Output_matrix(struct maze_matrix A)
{int i,j,m,n;
 i=A.rownum;
 j=A.colnum;
 printf("** The form of the maze which you have inputed is:");
 for(m=1;m<=i;m++)
   {printf("\n");
    for(n=1;n<=j;n++)
      {printf("%d   ",A.maze[m-1][n-1]);
      }
    printf("\n");
   }
 return 0;
}


ADJLIST create_adjlist(struct maze_matrix A)
{
    ADJLIST G;
    int m,n,i,j;
    int a=1;
    struct listnode *p,*q;
    i=A.rownum;
    j=A.colnum;
    G.vexnum=i*j;
    for(m=1;m<=i;m++)
        for(n=1;n<=j;n++)
        {

            G.adj[a].data=(m-1)*j+n;
            G.adj[a].first=NULL;
            if(A.maze[m-1][n-1]==0)
            {
                if(m<i)
                {
                   if(A.maze[m][n-1]==0)
                   {
                            p=(struct listnode *)malloc(sizeof(ADJLIST));
                            p->adjno=m*j+n;
                            p->next=NULL;
                            G.adj[a].first=p;

                   }
                }
                if(n<j)
                {
                    if(A.maze[m-1][n]==0)
                    {
                        if(m<i&&A.maze[m][n-1]==0)
                        {
                            q=(struct listnode*)malloc(sizeof(ADJLIST));
                            q->adjno=(m-1)*j+n+1;
                            p->next=q;
                            p=q;
                            p->next=NULL;
                        }
                        else
                        {
                            p=(struct listnode*)malloc(sizeof(ADJLIST));
                            p->adjno=(m-1)*j+n+1;
                            p->next=NULL;
                            G.adj[a].first=p;
                        }

                    }
                }
                if(n>1)
                {
                    if(A.maze[m-1][n-2]==0)
                    {
                        if(
                            (m<i&&A.maze[m][n-1]==0)||
                            (n<j&&A.maze[m-1][n]==0)
                           )
                        {
                            q=(struct listnode*)malloc(sizeof(ADJLIST));
                            q->adjno=(m-1)*j+n-1;
                            p->next=q;
                            p=q;
                            p->next=NULL;
                         }
                         else
                         {
                            p=(struct listnode *)malloc(sizeof(ADJLIST));
                            p->adjno=(m-1)*j+n-1;
                            p->next=NULL;
                            G.adj[a].first=p;
                         }

                    }
                }
                if(m>1)
                {
                    if(A.maze[m-2][n-1]==0)
                     {
                        if(
                              (m<i&&A.maze[m][n-1]==0)||
                              (n<j&&A.maze[m-1][n]==0)||
                              (n>1&&A.maze[m-1][n-2]==0)
                          )
                        {
                             q=(struct listnode*)malloc(sizeof(ADJLIST));
                             q->adjno=(m-2)*j+n;
                             p->next=q;
                             p=q;
                             p->next=NULL;
                        }
                        else
                        {
                               p=(struct listnode *)malloc(sizeof(ADJLIST));
                                p->adjno=(m-2)*j+n;
                               p->next=NULL;
                               G.adj[a].first=p;
                        }
                    }
                   }
                 }


             a++;
        }
    return (G);
  }


int Gothrough(int *col,ADJLIST G,int *a,int *b)
  {
    List pre;
    int front=0,rear=1;
    int flag=1;
    int v;
    struct listnode *p;
    pre[*a]=0;
    visited[*a]=1;
    queue[rear]=*a;

    while(front!=rear&&flag!=0)
    {front=(front+1)%MAXVER;
     v=queue[front];
     p=G.adj[v].first;
     while(p!=NULL&&p->adjno!=*b)
       {if(visited[p->adjno]==0)
	  {visited[p->adjno]=1;
	   rear=(rear+1)%MAXVER;
	   queue[rear]=p->adjno;
	   pre[p->adjno]=queue[front];
	  }
	p=p->next;
       }
        if(p->adjno==*b)
	  {flag=0;
	  }

    }
     if(p->adjno==*b)
     {
        rear++;
        queue[rear]=*b;
        pre[*b]=queue[front];
	printf("== The path is:\n");
        output_line(*acol,pre,*b);
     }
     if(front==rear)
      {
	printf("** Sorry! Can not find the path!\n");
      }
    printf("\n");
	return 0;
}

int output_line(int *acol,List pre,int *b)
{
	int verno,row,col;
	int n=0;
	verno=*b;
	printf("     ");
	while(verno!=0)
	{
		row=(verno-1)/(*acol)+1;
		col=(verno-1)%(*acol)+1;
		printf("[%d,%d]",row,col);
		verno=pre[verno];
		n++;
		if(n%5==0)
			printf("\n");
		if(verno!=0)
			printf("<--");
	}
	printf("\n\n");
	printf("                                         Press any key to Quit...\n");
	return 0;
}


int main()
{int *col;
 char ch;
 printf("===============================================================================\n");/* from 10 to 88 */
 printf("==                     __________________                                    ==\n");
 printf("==                     |  STROLL  MAZE  |                                    ==\n");
 printf("==                     ------------------                                    ==\n");
 printf("==                                                                           ==\n");
 printf("==                                                                           ==\n");
 printf("==                                                                           ==\n");
 printf("==                                                 ----Written By: Gui Ripei ==\n");
 printf("==       HuBei Polytechnic University,Computer Science And Technology        ==\n");
 printf("==                                       ----Academic Advisor: Zhang Shengli ==\n");
 printf("==                                                        ** Date: 2004.9.23 ==\n");
 printf("===============================================================================\n");
 printf("** EXPLANATION:\n");
 printf("       In this program,you can input the digit 0 and 1 to set up a maze which\n");
 printf("   you want.Then,you must input the entry' and the exit' direction,but they mu-\n");
 printf("   st can get pass.So the coordinate of entry and exit are (0,0).\n");
 printf("\n");
 printf("** Do you want to continue?\n");
 printf("** Please input your selection(Y/N):");
 scanf("%c",&ch);
 if(ch=='y'||ch=='y')
   {struct maze_matrix A;
    ADJLIST G;
    int *mazein,*mazeout;
    int a,b,c;
    mazein=&a;
    mazeout=&b;
    col=&c;
    A=Input_matrix(mazein,mazeout);
    //clrscr();
    *col=A.colnum;
    Output_matrix(A);
    G=create_adjlist(A);
    Gothrough(col,G,mazein,mazeout);
    getch();
   }
 if(ch=='N'||ch=='n')
   {exit(1);
   }
 return 0;
}