migong.cpp

学习中自己编的一些小程序

 /*
  Name: 迷宫 
  Copyright: 
  Author: 刘崇军 
  Date: 09-11-08 21:51
  Description:
*/
#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
#include<malloc.h> 
#define max 100
#define da 10
#define db 10
typedef int datatype;


typedef struct{
        
       int top;   //栈顶位置； 
       datatype x[max],y[max];  
       }stack;
void Chushihua(stack *s)
{
     s->top=-1;
   //  printf("初始化成功");
    // return 1;
     
}
int In(stack *s,int a,int b)
{  // int a,b;
   if (s->top>=max-1)              //上溢
   {
	     printf("stack overflow!\n");
         return 0;
   }
  	else
	{
		s->top++;
        s->x[s->top]=a;
        s->y[s->top]=b;
	//	mi[a][b]=99;
		return 1;
	}
    //mi[a][b]=99;
}
int out(stack *s)
{
  	if (s->top<=-1)                          //下溢
    	{printf("stack underflow!\n");return 0;}
  	else
    	{ 	s->top--;
      		return 1;
    	}
}
void SC(stack *s)
{
	int i;
	for(i=0;i<=s->top;i++)
	printf("(%d,%d)",s->x[i],s->y[i]);
	//if(i==s->top)
     //	printf("(%d,%d)",s->x[i],s->y[i]);
}
void Lu(stack *s,int mi[da][db])
{  // stack m=s;
	int i,m,test;
	//int count=0;
	int dq,dp,dm,dn;
	int g,h;
    int direction[4][2]={{0,1},{1,0},{0,-1},{-1,0}};

   while(s->top>-1)
   {
      
	   for(i=0;i<4;i++)
	   {
		   dq=s->x[s->top];
		   dp=s->y[s->top];
           g=dq+direction[i][0];
		   h=dp+direction[i][1];	  
		   if(g>=0&&h>=0&&mi[g][h]==0)
		   {
			   //mi[g][h]=99;
			   dm=g;dn=h;
			   test=0;			/*判断搜索到的点是否在栈中已经出现，避免出现死循环*/
				for(m=0;m<=s->top;m++)
				{ 
					if(g==s->x[m]&&h==s->y[m])
						test=1;
				}
				if(test==0)
				{
			       In(s,dm,dn); 
                   if(g==8&&h==8)
				    SC(s);
                   else
				   Lu(s,mi);
				}
			      //mi[g][h]=99;
		   }
		 
		   
	   }   
     //mi[s->x[s->top]][s->y[s->top]]=3;
	  out(s);
   } 
}

int main()
{
//	int i,j;
    stack s;
	int mi[10][10]={{1,1,1,1,1,1,1,1,1,1},
                {1,0,0,0,1,0,1,0,0,1},
                {1,1,0,1,0,1,0,1,0,1},
                {1,0,0,1,0,1,0,0,1,1},
                {1,1,0,1,0,0,1,1,0,1},
                {1,1,0,0,0,0,0,1,0,1},
                {1,1,1,1,0,1,0,1,0,1},
                {1,1,0,0,0,0,0,0,0,1},
                {1,1,0,1,0,1,0,1,0,1},
                {1,1,1,1,1,1,1,1,1,1}
               };
    printf("迷宫如下（1表示墙壁，0表示通道。）:\n");
    printf("1,1,1,1,1,1,1,1,1,1\n");
    printf("1,0,0,0,1,0,1,0,0,1\n");
    printf("1,1,0,1,0,1,0,1,0,1\n");
    printf("1,0,0,1,0,1,0,0,1,1\n");
    printf("1,1,0,1,0,0,1,1,0,1\n");
    printf("1,1,0,0,0,0,0,1,0,1\n");
    printf("1,1,1,1,0,1,0,1,0,1\n");
    printf("1,1,0,0,0,0,0,0,0,1\n");
    printf("1,1,0,1,0,1,0,1,0,1\n");
    printf("1,1,1,1,1,1,1,1,1,1\n");
    printf("(1,1) (8,8)分别为入口，出口。\n");
    Chushihua(&s);
    s.top++;
	s.x[s.top]=1;
	s.y[s.top]=1;
   //mi[1][1]=99;
    Lu(&s,mi);
    system("pause");
    return 1;
}