API tools faq
paste
Advertisement
Noam_15

Solve_The_Maze_V002

Noam_15
Jun 21st, 2018
191
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 11.90 KB | None | 0 0
raw download clone embed print report
  1. // Solve The Maze
  2. // V0.0.2
  3. //
  4. // Date: 2018.06.21
  5. // (Based on: https://symbolsprogrammingblog.wordpress.com/2010/06/20/%D7%9E%D7%A6%D7%99%D7%90%D7%AA-%D7%94%D7%93%D7%A8%D7%9A-%D7%94%D7%A7%D7%A6%D7%A8%D7%94-%D7%91%D7%99%D7%95%D7%AA%D7%A8-%D7%91%D7%9E%D7%91%D7%95%D7%9A/ )
  6.  
  7. #include <stdio.h>
  8. #include <time.h>
  9.  
  10. #define HEIGHT   50
  11. #define WIDTH    9
  12.  
  13. #define WALL     -1
  14. #define PATH     0
  15. #define START    83  // 'S'
  16. #define END      69  // 'E'
  17. #define ARROW    176
  18.  
  19. #define UP       30
  20. #define DOWN     40
  21. #define RIGHT    50
  22. #define LEFT     60
  23.  
  24. #define true 1
  25. #define false 0
  26. typedef int Boolean;
  27.  
  28.  
  29. struct Point {
  30.    int Row;
  31.    int Column;
  32. };
  33.  
  34. int SolveMaze(int Maze[HEIGHT][WIDTH]);
  35. struct Point FindStartingPoint(int Maze[HEIGHT][WIDTH]);
  36. struct Point FindStartingPathPoint(int Maze[HEIGHT][WIDTH]);
  37. int SolveMazeREC(int Maze[HEIGHT][WIDTH], int h, int w, Boolean saveChanges);
  38. void ShowBoard(int Board[HEIGHT][WIDTH]);
  39. void CopyBoard(int targetBoard[HEIGHT][WIDTH], int sourceBoard[HEIGHT][WIDTH]);
  40.  
  41. // This function try to solve the maze with minimum steps.
  42. //
  43. // If succeeded - fill the given board with 'ARROW' in the path that is found,
  44. //                and return the number of steps.
  45. // If failed    - return -1
  46. int SolveMaze(int Maze[HEIGHT][WIDTH])
  47. {
  48.     int h, w;
  49.     int steps = 2;
  50.     int lowestSteps = -1;
  51.     int lowestStepsSide = DOWN;
  52.     int NewMaze[HEIGHT][WIDTH];
  53.     int tmp;
  54.     struct Point startingPathPoint;
  55.     struct Point startingPoint;
  56.  
  57.  
  58.     // Search start position
  59.     startingPathPoint = FindStartingPathPoint(Maze);
  60.     startingPoint = FindStartingPoint(Maze);
  61.     h = startingPathPoint.Row;
  62.     w = startingPathPoint.Column;
  63.  
  64.     // So the START position will not bother us
  65.     Maze[startingPoint.Row][startingPoint.Column] = ARROW;
  66.  
  67.     Maze[h][w] = ARROW;
  68.  
  69.     // UP
  70.     if (Maze[h-1][w] != WALL && Maze[h-1][w] != ARROW)
  71.     {
  72.         CopyBoard(NewMaze, Maze);
  73.         tmp = SolveMazeREC(NewMaze, h-1, w, false, NULL);
  74.         if (tmp != -1)
  75.             if (tmp < lowestSteps || lowestSteps == -1)
  76.             {
  77.                 lowestSteps = tmp;
  78.                 lowestStepsSide = UP;
  79.             }
  80.                
  81.     }
  82.  
  83.     // DOWN
  84.     if (Maze[h+1][w] != WALL && Maze[h+1][w] != ARROW)
  85.     {
  86.         CopyBoard(NewMaze, Maze);
  87.         tmp = SolveMazeREC(NewMaze, h+1, w, false, NULL);
  88.         if (tmp != -1)
  89.             if (tmp < lowestSteps || lowestSteps == -1)
  90.             {
  91.                 lowestSteps = tmp;
  92.                 lowestStepsSide = DOWN;
  93.             }
  94.     }
  95.  
  96.     // RIGHT
  97.     if (Maze[h][w+1] != WALL && Maze[h][w+1] != ARROW)
  98.     {
  99.         CopyBoard(NewMaze, Maze);
  100.         tmp = SolveMazeREC(NewMaze, h, w+1, false, NULL);
  101.         if (tmp != -1)
  102.             if (tmp < lowestSteps || lowestSteps == -1)
  103.             {
  104.                 lowestSteps = tmp;
  105.                 lowestStepsSide = RIGHT;
  106.             }
  107.     }
  108.    
  109.     // LEFT
  110.     if (Maze[h][w-1] != WALL && Maze[h][w-1] != ARROW)
  111.     {
  112.         CopyBoard(NewMaze, Maze);
  113.         tmp = SolveMazeREC(NewMaze, h, w-1, false, NULL);
  114.         if (tmp != -1)
  115.             if (tmp < lowestSteps || lowestSteps == -1)
  116.             {
  117.                 lowestSteps = tmp;
  118.                 lowestStepsSide = LEFT;
  119.             }
  120.     }
  121.  
  122.  
  123.  
  124.     // (If all directions are blocked, lowestSteps = -1)
  125.     if (lowestSteps == -1)
  126.     {
  127.         // Reset the START position // (We dont realy need this here)
  128.         Maze[startingPoint.Row][startingPoint.Column] = START;
  129.  
  130.         return -1;
  131.     }
  132.     else
  133.     {
  134.         switch(lowestStepsSide)
  135.         {
  136.             case UP  :
  137.                 SolveMazeREC(NewMaze, h-1, w, true, Maze);
  138.                 break;
  139.  
  140.             case DOWN  :
  141.                 SolveMazeREC(NewMaze, h+1, w, true, Maze);
  142.                 break;
  143.  
  144.             case RIGHT :
  145.                 SolveMazeREC(NewMaze, h, w+1, true, Maze);
  146.                 break;
  147.  
  148.             case LEFT :
  149.                 SolveMazeREC(NewMaze, h, w-1, true, Maze);
  150.                 break;
  151.         }
  152.  
  153.         // Reset the START position
  154.         Maze[startingPoint.Row][startingPoint.Column] = START;
  155.         return steps + lowestSteps;
  156.     }
  157.    
  158. }
  159.  
  160. struct Point FindStartingPoint(int Maze[HEIGHT][WIDTH])
  161. {
  162.     int startRow;
  163.     int startColumn;
  164.     struct Point StartingPoint;
  165.     for (startRow = 0; startRow < HEIGHT; startRow++)
  166.     {
  167.         for (startColumn = 0; startColumn < WIDTH; startColumn++)
  168.         {
  169.             if (Maze[startRow][startColumn] == START)
  170.             {
  171.                 StartingPoint.Column = startColumn;
  172.                 StartingPoint.Row = startRow;
  173.                 return StartingPoint;
  174.             }
  175.         }
  176.     }
  177.  
  178.     printf("Error in  FindStartingPoint\n");
  179.     return StartingPoint;
  180. }
  181.  
  182. struct Point FindStartingPathPoint(int Maze[HEIGHT][WIDTH])
  183. {
  184.     struct Point StartingPathPoint;
  185.     StartingPathPoint = FindStartingPoint(Maze);
  186.  
  187.     if (Maze[StartingPathPoint.Row + 1][StartingPathPoint.Column] == PATH)
  188.     {
  189.         StartingPathPoint.Row += 1;
  190.         return StartingPathPoint;
  191.     }
  192.     else if (Maze[StartingPathPoint.Row - 1][StartingPathPoint.Column] == PATH)
  193.     {
  194.         StartingPathPoint.Row -= 1;
  195.         return StartingPathPoint;
  196.     }
  197.     else if (Maze[StartingPathPoint.Row][StartingPathPoint.Column + 1] == PATH)
  198.     {
  199.         StartingPathPoint.Column += 1;
  200.         return StartingPathPoint;
  201.     }
  202.     else if (Maze[StartingPathPoint.Row][StartingPathPoint.Column - 1] == PATH)
  203.     {
  204.         StartingPathPoint.Column -= 1;
  205.         return StartingPathPoint;
  206.     }
  207.     else
  208.     {
  209.         printf("Error in  FindStartingPathPoint\n");
  210.         return StartingPathPoint;
  211.     }
  212. }
  213.  
  214.  
  215.  
  216. int SolveMazeREC(int Maze[HEIGHT][WIDTH], int h, int w, Boolean saveChanges, int MainMaze[HEIGHT][WIDTH])
  217. {
  218.     int lowestSteps = -1;
  219.     int NewMaze[HEIGHT][WIDTH];
  220.     int lowestStepsSide = DOWN;
  221.     int tmp;
  222.  
  223.     // -- END
  224.     if (Maze[h][w] == END)
  225.         return 1;
  226.  
  227.     Maze[h][w] = ARROW;
  228.     if (saveChanges == true)
  229.     {
  230.         MainMaze[h][w] = ARROW;
  231.     }
  232.  
  233.     // UP
  234.     if (Maze[h-1][w] != WALL && Maze[h-1][w] != ARROW)
  235.     {
  236.         CopyBoard(NewMaze, Maze);
  237.         tmp = SolveMazeREC(NewMaze, h-1, w, false, NULL);
  238.         if (tmp != -1)
  239.             if (tmp < lowestSteps || lowestSteps == -1)
  240.             {
  241.                 lowestSteps = tmp;
  242.                 lowestStepsSide = UP;
  243.             }
  244.     }
  245.  
  246.     // DOWN
  247.     if (Maze[h+1][w] != WALL && Maze[h+1][w] != ARROW)
  248.     {
  249.         CopyBoard(NewMaze, Maze);
  250.         tmp = SolveMazeREC(NewMaze, h+1, w, false, NULL);
  251.         if (tmp != -1)
  252.             if (tmp < lowestSteps || lowestSteps == -1)
  253.             {
  254.                 lowestSteps = tmp;
  255.                 lowestStepsSide = DOWN;
  256.             }
  257.     }
  258.  
  259.     // RIGHT
  260.     if (Maze[h][w+1] != WALL && Maze[h][w+1] != ARROW)
  261.     {
  262.         CopyBoard(NewMaze, Maze);
  263.         tmp = SolveMazeREC(NewMaze, h, w+1, false, NULL);
  264.         if (tmp != -1)
  265.             if (tmp < lowestSteps || lowestSteps == -1)
  266.             {
  267.                 lowestSteps = tmp;
  268.                 lowestStepsSide = RIGHT;
  269.             }
  270.     }
  271.    
  272.     // LEFT
  273.     if (Maze[h][w-1] != WALL && Maze[h][w-1] != ARROW)
  274.     {
  275.         CopyBoard(NewMaze, Maze);
  276.         tmp = SolveMazeREC(NewMaze, h, w-1, false, NULL);
  277.         if (tmp != -1)
  278.             if (tmp < lowestSteps || lowestSteps == -1)
  279.             {
  280.                 lowestSteps = tmp;
  281.                 lowestStepsSide = LEFT;
  282.             }
  283.     }
  284.  
  285.    
  286.     Maze[h][w] = PATH;
  287.     if (saveChanges == true)
  288.     {
  289.         if (lowestSteps != -1)
  290.         {
  291.             switch(lowestStepsSide)
  292.             {
  293.                 case UP  :
  294.                     SolveMazeREC(NewMaze, h-1, w, true, MainMaze);
  295.                     break;
  296.  
  297.                 case DOWN  :
  298.                     SolveMazeREC(NewMaze, h+1, w, true, MainMaze);
  299.                     break;
  300.  
  301.                 case RIGHT :
  302.                     SolveMazeREC(NewMaze, h, w+1, true, MainMaze);
  303.                     break;
  304.  
  305.                 case LEFT :
  306.                     SolveMazeREC(NewMaze, h, w-1, true, MainMaze);
  307.                     break;
  308.             }
  309.         }
  310.        
  311.     }
  312.    
  313.  
  314.     // (If all directions are blocked, lowestSteps = -1)
  315.     if (lowestSteps == -1)
  316.     {
  317.         return -1;
  318.     }
  319.     else
  320.     {
  321.         return 1 + lowestSteps;
  322.     }
  323. }
  324.  
  325.  
  326. void ShowBoard(int Board[HEIGHT][WIDTH])
  327. {
  328.     int row;
  329.     int col;
  330.  
  331.     printf("Full maze:\n\n\n");
  332.  
  333.     for (row = 0; row < HEIGHT; row++)    // Loop through every row
  334.     {
  335.         for (col = 0; col < WIDTH; col++) // And every column
  336.         {
  337.             switch(Board[row][col])
  338.             {
  339.                 case WALL  :
  340.                   putchar('\xDB');
  341.                   break;
  342.  
  343.                 case PATH  :
  344.                   putchar(' ');
  345.                   break;
  346.  
  347.                 case ARROW :
  348.                   putchar(ARROW);
  349.                   break;
  350.  
  351.                 case START :
  352.                   putchar(START);
  353.                   break;
  354.  
  355.                 case END   :
  356.                   putchar(END);
  357.                   break;
  358.  
  359.                default     :
  360.                   putchar('?');
  361.                   break;
  362.             }
  363.         }
  364.         putchar('\n');
  365.     }
  366.     printf("\n\n\n");
  367. }
  368.  
  369. void CopyBoard(int targetBoard[HEIGHT][WIDTH], int sourceBoard[HEIGHT][WIDTH])
  370. {
  371.     int i, j;
  372.     for (i = 0; i < HEIGHT; i++)
  373.     {
  374.         for (j = 0; j < WIDTH; j++)
  375.         {
  376.             targetBoard[i][j] = sourceBoard[i][j];
  377.         }
  378.     }
  379. }
  380.  
  381. void InitializeTheMaze(int Board[HEIGHT][WIDTH])
  382. {
  383.     int TmpBoard[HEIGHT][WIDTH] = {
  384.         { WALL , WALL , START, WALL, WALL , WALL , WALL , WALL , WALL  },
  385.         { WALL , PATH , PATH , PATH, PATH , PATH , PATH , PATH , WALL  },
  386.         { WALL , PATH , WALL , WALL, WALL , PATH , WALL , WALL , WALL  },
  387.         { WALL , PATH , WALL , PATH, WALL , PATH , PATH , PATH , WALL  },
  388.         { WALL , WALL , WALL , PATH, WALL , PATH , WALL , PATH , WALL  },
  389.         { WALL , PATH , WALL , PATH, PATH , PATH , PATH , PATH , WALL  },
  390.         { WALL , PATH , WALL , WALL, WALL , WALL , WALL , PATH , WALL  },
  391.         { WALL , PATH , PATH , PATH, PATH , PATH , PATH , PATH , WALL  },
  392.         { WALL , PATH , WALL , WALL, WALL , WALL , WALL , WALL , WALL  },
  393.         { WALL , PATH , PATH , PATH, PATH , PATH , PATH , PATH , WALL  },
  394.         { WALL , WALL , WALL , WALL, WALL , WALL , WALL , PATH , WALL  },
  395.         { WALL , PATH , PATH , PATH, PATH , PATH , PATH , PATH , WALL  },
  396.         { WALL , PATH , WALL , WALL, PATH , WALL , WALL , PATH , WALL  },
  397.         { WALL , PATH , PATH , PATH, PATH , PATH , PATH , PATH , WALL  },
  398.         { WALL , PATH , WALL , PATH, WALL , PATH , WALL , PATH , WALL  },
  399.         { WALL , PATH , WALL , PATH, PATH , PATH , WALL , PATH , WALL  },
  400.         { WALL , PATH , WALL , WALL, WALL , WALL , WALL , PATH , WALL  },
  401.         { WALL , PATH , PATH , PATH, PATH , PATH , PATH , PATH , WALL  },
  402.         { WALL , WALL , WALL , WALL, WALL , WALL , WALL , PATH , WALL  },
  403.         { WALL , PATH , PATH , PATH, PATH , PATH , WALL , PATH , WALL  },
  404.         { WALL , WALL , PATH , WALL, WALL , WALL , WALL , PATH , WALL  },
  405.         { WALL , PATH , PATH , PATH, WALL , PATH , PATH , PATH , WALL  },
  406.         { WALL , PATH , WALL , WALL, WALL , PATH , WALL , WALL , WALL  },
  407.         { WALL , PATH , PATH , PATH, WALL , PATH , PATH , PATH , WALL  },
  408.         { WALL , PATH , WALL , PATH, WALL , PATH , WALL , PATH , WALL  },
  409.         { WALL , PATH , WALL , PATH, PATH , PATH , PATH , PATH , WALL  },
  410.         { WALL , WALL , WALL , WALL, WALL , PATH , WALL , PATH , WALL  },
  411.         { WALL , PATH , PATH , PATH, PATH , PATH , PATH , PATH , WALL  },
  412.         { WALL , PATH , WALL , PATH, PATH , WALL , PATH , WALL , WALL  },
  413.         { WALL , PATH , PATH , PATH, WALL , WALL , PATH , WALL , WALL  },
  414.         { WALL , WALL , WALL , PATH, WALL , WALL , PATH , WALL , WALL  },
  415.         { WALL , PATH , PATH , PATH, PATH , WALL , PATH , PATH , WALL  },
  416.         { WALL , WALL , WALL , PATH, WALL , WALL , PATH , PATH , WALL  },
  417.         { WALL , PATH , PATH , PATH, WALL , WALL , WALL , PATH , WALL  },
  418.         { WALL , PATH , WALL , PATH, WALL , PATH , WALL , PATH , WALL  },
  419.         { WALL , PATH , WALL , PATH, PATH , PATH , PATH , PATH , WALL  },
  420.         { WALL , PATH , PATH , PATH, PATH , WALL , PATH , PATH , WALL  },
  421.         { WALL , PATH , WALL , PATH, PATH , PATH , PATH , PATH , WALL  },
  422.         { WALL , WALL , WALL , WALL, PATH , WALL , PATH , WALL , WALL  },
  423.         { WALL , PATH , PATH , PATH, PATH , WALL , PATH , PATH , WALL  },
  424.         { WALL , PATH , WALL , WALL, WALL , WALL , PATH , WALL , WALL  },
  425.         { WALL , PATH , PATH , PATH, WALL , PATH , PATH , PATH , WALL  },
  426.         { WALL , PATH , WALL , WALL, WALL , WALL , PATH , WALL , WALL  },
  427.         { WALL , PATH , PATH , PATH, WALL , PATH , PATH , PATH , WALL  },
  428.         { WALL , PATH , WALL , PATH, WALL , PATH , WALL , PATH , WALL  },
  429.         { WALL , PATH , WALL , PATH, PATH , PATH , PATH , PATH , WALL  },
  430.         { WALL , WALL , WALL , WALL, WALL , WALL , WALL , PATH , WALL  },
  431.         { WALL , PATH , PATH , PATH, PATH , PATH , PATH , PATH , WALL  },
  432.         { WALL , PATH , PATH , WALL, WALL , WALL , PATH , PATH , WALL  },
  433.         { WALL , END  , WALL , WALL, WALL , WALL , WALL , WALL , WALL  },
  434.     };
  435.  
  436.     CopyBoard(Board, TmpBoard);
  437. }
  438.  
  439. int main()
  440. {
  441.     int Board[HEIGHT][WIDTH];
  442.     int Steps;
  443.     clock_t begin, end;
  444.     double time_spent;
  445.  
  446.     InitializeTheMaze(Board);
  447.  
  448.     printf("* Start:\n\n");
  449.     ShowBoard(Board);
  450.  
  451.     printf("* Program Answer:\n\n");
  452.  
  453.     begin = clock();
  454.     Steps = SolveMaze(Board);
  455.     end = clock();
  456.     time_spent = (double)(end - begin) / CLOCKS_PER_SEC;
  457.  
  458.     if (Steps != -1) // Path found
  459.     {
  460.         printf("Number of steps: %d\n-----------------------\n", Steps);
  461.         ShowBoard(Board);
  462.     }
  463.     else
  464.     {
  465.         printf("Maze cannot be solved! :(\n\n");
  466.     }
  467.    
  468.     printf("Time:  %lf Seconds\n", time_spent);
  469.     getchar();
  470. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!