fork download 
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #define NUM_ROWS  8
  4. #define NUM_COLS  6
  5. #define BOUNDARY_COLS 8
  6. #define MAX_STACK_SIZE 100
  7. #define FALSE 0
  8. #define TRUE 1
  9. typedef struct {
  10. 	  short int row;
  11. 	  short int col;
  12. 	  short int dir;
  13. 	} element;
  14. element stack[MAX_STACK_SIZE];     /* global stack declaration */
  15. typedef struct {
  16. 	  short int vert;
  17.       short int horiz;
  18. 	} offsets;
  19. offsets move[9];   /* array of moves for each direction */
  20. static short int maze[][BOUNDARY_COLS] = {{1,1,1,1,1,1,1,1},   /* top boundary  */
  21. 				  {1,0,0,0,0,0,0,1},
  22. 				  {1,0,0,1,1,0,0,1},
  23. 				  {1,0,1,1,1,1,0,1},
  24. 				  {1,0,0,0,0,1,0,1},
  25. 				  {1,0,1,0,0,1,0,1},
  26. 				  {1,0,1,1,1,1,0,1},
  27. 				  {1,0,0,1,1,0,0,1},
  28. 				  {1,0,0,0,0,0,0,1},
  29. 				  {1,1,1,1,1,1,1,1}};  /* bottom boundary */
  30. short int mark[][BOUNDARY_COLS] = {{0,0,0,0,0,0,0,0},
  31. 				  {0,0,0,0,0,0,0,0},
  32. 				  {0,0,0,0,0,0,0,0},
  33. 				  {0,0,0,0,0,0,0,0},
  34. 				  {0,0,0,0,0,0,0,0},
  35. 				  {0,0,0,0,0,0,0,0},
  36. 				  {0,0,0,0,0,0,0,0},
  37. 				  {0,0,0,0,0,0,0,0},
  38. 				  {0,0,0,0,0,0,0,0},
  39. 				  {0,0,0,0,0,0,0,0}};
  40. int top;
  41. void init_move();
  42. void add(element);
  43. element delete1();
  44. void stack_full();
  45. void stack_empty();
  46. void path();
  47. void print_record(int,int,int);
  48. void print_maze();	
  49. int main ()
  50. {/* stack represented as an array */  		
  51.   init_move();
  52.   print_maze();
  53.   path();
  54.   system ("pause");
  55. }
  56.  
  57. void init_move()
  58. {/* initial the table for the next row and column moves */
  59.    move[1].vert = -1;  move[1].horiz =  0;   /*  N */
  60.    move[2].vert = -1;  move[2].horiz =  1;   /* NE */
  61.    move[3].vert =  0;  move[3].horiz =  1;   /*  E */
  62.    move[4].vert =  1;  move[4].horiz =  1;   /* SE */
  63.    move[5].vert =  1;  move[5].horiz =  1;   /*  S */
  64.    move[6].vert =  1;  move[6].horiz =  0;   /* SW */
  65.    move[7].vert =  0;  move[7].horiz = -1;   /*  W */
  66.    move[8].vert = -1;  move[8].horiz = -1;   /* NW */
  67. }
  68.  
  69. void print_maze()
  70. {/* print out the maze */
  71.   int i,j;
  72.   //printf("Your maze, with the boundaries is: \n\n");
  73.   for (i = 0; i <= NUM_ROWS+1; i++) {
  74.     for(j = 0; j <= NUM_COLS+1; j++)
  75.       printf("%2d",maze[i][j]);
  76.     printf("\n");
  77.   }
  78. }
  79. void stack_full()
  80. {
  81.    printf("The stack is full.  No item added \n");
  82. }
  83. void stack_empty()
  84. {
  85.   printf("The stack is empty.  No item deleted \n");
  86. }
  87. void add(element item)
  88. { /* add an item to the global stack
  89.      top (also global) is the current top of the stack,
  90.      MAX_STACK_SIZE is the maximum size */
  91.    if (top == MAX_STACK_SIZE)
  92.      stack_full();
  93.    else
  94.       stack[++top] = item;
  95. }
  96.  
  97. element delete1()
  98. { /* remove top element from the stack and put it in item */
  99.   if (top < 0)
  100.     stack_empty();
  101.   else
  102.     return stack[top--];
  103. }
  104.  
  105. void print_record(int row, int col, int dir)
  106. { /* print out the row, column, and the direction, the direction
  107.    is printed out with its numeric equivvalent */
  108.        printf("%2d    %2d%5d", dir,row, col);
  109.        switch (dir-1) {
  110.        case 1: printf("    N");
  111. 	      break;
  112.        case 2: printf("    NE");
  113. 	       break;
  114.        case 3: printf("    E ");
  115. 	       break;
  116.        case 4: printf("    SE");
  117. 	       break;
  118.        case 5: printf("    S ");
  119. 	       break;
  120.        case 6: printf("    SW");
  121. 	       break;
  122.        case 7: printf("    W ");
  123. 	       break;
  124.        case 8: printf("    NW");
  125. 	       break;
  126.        }
  127.        printf("\n");
  128. }
  129.  
  130.  
  131. void path()
  132. {/*  output a path through the maze if such a path exists,
  133.     the maze is found in positions 1 to NUM_ROWS and 1 to NUM_COLS.
  134.     Rows 0 and NUM_ROWS+1 serve as boundaries, as do Columns
  135.     0 and NUM_COLS+1. */
  136.   int i, row, col, next_row, next_col, dir, found = FALSE;
  137.   element position;
  138.   mark[0][0] = 1;
  139.   /* place the starting position, maze[1][1] onto the stack
  140.      starting direction is 2  */
  141.   top = 0;
  142.   stack[0].row = 0;  stack[0].col = 0;  stack[0].dir = 2;
  143.   while (top > -1 && !found) {
  144.     /* remove position at top of stack, and determine if
  145. 	there is a path from this position */
  146.     position = delete1();
  147.     row = position.row;  col = position.col; dir = position.dir;
  148.     while (dir <=  8 && !found) {
  149.     /* check all of the remaining directions from the current
  150.     position */
  151.       next_row = row + move[dir].vert;
  152.       next_col = col + move[dir].horiz;
  153.       if (next_row == NUM_ROWS && next_col == NUM_COLS)
  154.       /* path has been found, exit loop and print it out */
  155. 	found = TRUE;
  156.       else if ( !maze[next_row][next_col]
  157. 	    &&  !mark[next_row][next_col]) {
  158.       /* current position has not been checked, place it
  159. 	 on the stack and continue */
  160. 	 mark[next_row][next_col] = 1;
  161. 	 position.row = row;	 position.col = col;
  162. 	 position.dir = ++dir;
  163. 	 add(position);
  164. 	 row = next_row;	 col = next_col;	 dir = 1;
  165.        }
  166.        else
  167. 	 ++dir;
  168.      }
  169.    }
  170.    if (!found)
  171.      printf("The maze does not have a path\n");
  172.    else {
  173.    /* print out the path which is found in the stack */
  174.      printf("The maze traversal is: \n\n");
  175.      printf("dir#  row  col  dir\n\n");
  176.      for (i = 0; i <= top; i++)
  177.        print_record(stack[i].row, stack[i].col, stack[i].dir);
  178.      printf("      %2d%5d\n",row,col);
  179.      printf("      %2d%5d\n",NUM_ROWS,NUM_COLS);
  180.    }   
  181. }
Success #stdin #stdout 0.01s 5312KB
comments (?)
stdin 
Standard input is empty
stdout 
 1 1 1 1 1 1 1 1
 1 0 0 0 0 0 0 1
 1 0 0 1 1 0 0 1
 1 0 1 1 1 1 0 1
 1 0 0 0 0 1 0 1
 1 0 1 0 0 1 0 1
 1 0 1 1 1 1 0 1
 1 0 0 1 1 0 0 1
 1 0 0 0 0 0 0 1
 1 1 1 1 1 1 1 1
The maze traversal is: 

dir#  row  col  dir

 5     0    0    SE
 4     1    1    E 
 4     1    2    E 
 4     1    3    E 
 4     1    4    E 
 4     1    5    E 
 7     1    6    SW
 7     2    6    SW
 7     3    6    SW
 7     4    6    SW
 7     5    6    SW
 7     6    6    SW
       7    6
       8    6
https://ideone.com/TkCat
language:
C++ (gcc 8.3)
created:
13 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!