【高品質コード実践】【スタック】迷宮ゲーム

/*
                               
   ：use.c
  ：       ，      ————“ ”     ，      。
    ：2012-7-1  23:55
  ：  
    ：1.2
*/
#include <stdio.h>
#include "stack.h"

//        ，1    ，0    
int maze[M][N] = {  0, 0, 0, 1, 1, 1,
                    0, 1, 0, 0, 1, 1,
                    1, 0, 1, 0, 0, 0,
                    1, 0, 1, 0, 1, 0,
                    1, 1, 1, 1, 1, 0,
                    1, 1, 1, 1, 1, 0};

seqstack seq;// 
seqstack *s; //   
datatype temp; //      

int main()
{
     //int i = 0;
     //int j = 0;
     int r = 0;

     //           x, y, d
                    //   j, i
     datatype move[4] = {0, 1, 0, "RIGHT",
                         1, 0, 1, "DOWN",
                         0, -1, 2, "LEFT",
                         -1, 0, 3, "UP"};
     s = &seq;


     r = mazepath(maze, move);//          

     if(r == 1)
     {
          printf("the valid paht is (step from exit to entry):
");
          while(!empty_stack(s))
          {
               pop_stack(s, &temp);//      temp ，     
               printf("<%d, %2d>, %s
", temp.x, temp.y, move[temp.d].dir);
          }
     }
     else
     {
          printf("there is not a valid path!
");
     }
     return 0;
}

/*
                               
   ：stack.h
  ：      ，    ，     ，      
    ：2012-7-1  23:55
  ：  
    ：1.2
*/
#ifndef STACK_H_INCLUDED
#define STACK_H_INCLUDED
#define M 6//       
#define N 6 //        
#define MAXSIZE 2000//      

/*
    
x,y      ；
d         ；
dir d     
*/
typedef struct datatype
{
     int x;
     int y;
     int d;
     char dir[6];
}datatype;

/*
data[]    ；
top    ，           ！
*/
typedef struct seqstack
{
     datatype data[MAXSIZE];
     int top;
}seqstack;


//         
int mazepath(int maze[][N], datatype *move);
//  
int push_stack(seqstack *s, datatype x);
//       
int empty_stack(seqstack *s);
//  
int pop_stack(seqstack *s, datatype *x);
#endif // STACK_H_INCLUDED

/*
                               
   ：stack.c
  ：    ，      ，  ，  ，    
    ：2012-7-1  23:55
  ：  
    ：1.2
*/
#include <stdio.h>
#include "stack.h"
//    
#define RIGHT 0
#define DOWN 1
#define LEFT 2
#define UP   3
#define DIRECTIONS 4

seqstack seq;
seqstack *s;
datatype temp;

/*
    ——  ：
        ，       ，  ，      ，          ， ，  ，    
    ，         ，  ，  ，      ，      。
*/
int mazepath(int maze[][N], datatype move[])
{
     //         
     int x = 0;
     int y = 0;
     //i , j          biao;     
     int d = -1;
     int i = 0;
     int j = 0;
     //     
     temp.x = 0;
     temp.y = 0;
     temp.d = -1;
     maze[0][0] = -1; //        

     push_stack(s, temp);//  temp    

     while(!empty_stack(s))
     {
          pop_stack(s, &temp);//      temp，    
          x = temp.x;
          y = temp.y;
          d = temp.d + 1;     //  

          while(d < DIRECTIONS)//    4            
          {
               /*
               funtions:for location
               if it reaches the boundary, it will change directions in the order of RIGHT, DOWN, LEFT,UP.
               otherwise,
               go right, j + 1;
               go left,  j - 1;
               go up, i - 1;
               go down, i + 1;
               */
               switch(d)
               {
                    case RIGHT : if (y == N - 1) //   ,N    
                                 {
                                      d++;   //       
                                 }
                                 else
                                 {
                                      j = y + move[d].y;   //j = 1
                                 }
                                 i = x + move[d].x;        //i = 0
                                 break;
                    case DOWN : if (x == M - 1)  //    
                                {
                                     d++;
                                }
                                else
                                {
                                     i = x + move[d].x;    //i = 1
                                }
                                j = y + move[d].y;         //j = 0
                                break;
                   case LEFT : if (x == 0)      //    
                               {
                                    d++;
                               }
                               else
                               {
                                   i = x + move[d].x;      //i = -1
                               }
                               j = y + move[d].y;          //j = 0
                               break;
                   case UP : if (y == 0)        //    
                             {
                                  d++;
                             }
                             else
                             {
                                  j = y + move[d].y;        //j = -1
                             }
                             i = x + move[d].x;             //i = 0
                             break;

                   default : printf("direction error!
");
                            break;
               }

               if (maze[i][j] == 0)     //next direction is securable
               {
                    //      ，  
                    temp.x = x;
                    temp.y = y;
                    temp.d = d;
                    maze[x][y] = -1;  //mark visitd position
                    push_stack(s, temp); //push temp into stack

                    //       
                    x = i;
                    y = j;
                    //        ？
                    if ((x + 1) == M && (y + 1) == N) //find one pace
                    {
                         return 1;
                    }
                    else
                    {
                         d = 0;//      
                    }
               }
               else
               {
                    d++;    //             ，      
               }
          }
     }
     return 0;
}

/*
  
  ：   seqstack *s,  datatype x
  ：1，      ，0      ；
*/
int push_stack(seqstack *s, datatype x)
{
     //     
     if ( MAXSIZE - 1 == s->top )
     {
          return 0;
     }

     else
     {
          s->top++; //    
          s->data[s->top] = x;
          return 1;
     }
}
/*
        ，     ‘   ’
  ：   seqstack *s
  ：1，    ；0，     。
*/
int empty_stack(seqstack *s)
{
     if (0 == s->top)
     {
          return 1;
     }
     else
     {
          return 0;
     }
}
/*
  
  ：   sqstack *s,    datatype *x
*/
int pop_stack(seqstack *s, datatype *x)
{
     if(empty_stack(s))
     {
          return 0;
     }
     else
     {
          *x = s->data[s->top]; //       ，       
          s->top--;
          return 1;
     }
}