Barkai Class: מציאת הפתרון המהיר ביותר למבוך

הפתרון המהיר ביותר למבוך

הקוד הבא הוא למעשה חידה מפורסמת. נתקלתי בו בבלוג של Symbol/Skyance, ועם שינויים מסוימים אני מביא אותו לכם.

נתון מבוך שמיוצג ע"י מטריצה NxM כאשר תמיד תחילת המבוך בקואורדינטות (0,0) והסיום בקואורדינטות (N-1,M-1).
ערך של 1- באיבר במטריצה מייצג קיר שאי אפשר לעבור וערך של 0 מייצג דרך שאפשר לעבור בה.
לשם הפשטות מותר ללכת במבוך רק בקוים ישרים.

עליכם לכתוב תוכנית מחשב שתמצא את הדרך הקצרה ביותר שניתן ללכת בה במבוך מההתחלה עד לסיום.

מבוך לדוגמה - לפני הפתרון:

אחרי הפתרון:

כעת אתן לכם את הקוד שעושה הכל חוץ מלפתור את החידה.
(הקוד זמין גם כאן)

עליכם למלא את הפונקציה ()SolveMaze.
מומלץ לחשוב בצורה רקורסיבית.

// This code is waiting for you!
// Fill the function "SolveMaze()" with your code so it will correctly solve the maze in the shortest way!
 
 
 
 
#include <stdio.h>
 
#define HEIGHT   50
#define WIDTH    9
 
#define WALL     -1
#define PATH     0
#define START    83  // 'S'
#define END      69  // 'E'
#define ARROW    176 //  ░
 
 
// This function try to solve the maze with minimum steps.
//
// If succeeded - fill the given board with 'ARROW' in the path that is found,
//      and return the number of steps.
// If failed - return -1
int SolveMaze(int Maze[HEIGHT][WIDTH])
{
 // ***********
 // Your Code!
 // ***********
 
 
 // For example:
 Maze[1][2] = ARROW; // 1
 Maze[1][3] = ARROW; // 2
 Maze[1][4] = ARROW; // 3
 Maze[1][5] = ARROW; // 4
 Maze[2][5] = ARROW; // 5
 Maze[3][5] = ARROW; // 6
 // ...
 return 6;
}
 
 
void ShowBoard(int Board[HEIGHT][WIDTH])
{
 int row;
 int col;
 
 printf("Full maze:\n\n\n");
 
 for (row = 0; row < HEIGHT; row++)    // Loop through every row
 {
  for (col = 0; col < WIDTH; col++) // And every column
  {
   switch(Board[row][col])
   {
    case WALL  :
      putchar('\xDB');
      break;
 
    case PATH  :
      putchar(' ');
      break;
 
    case ARROW :
      putchar(ARROW);
      break;
 
       case START :
      putchar(START);
      break;
 
       case END   :
      putchar(END);
      break;
 
      default    :
      putchar('?');
      break;
   }
  }
  putchar('\n');
 }
 printf("\n\n\n");
}
 
void CopyBoard(int targetBoard[HEIGHT][WIDTH], int sourceBoard[HEIGHT][WIDTH])
{
 int i, j;
 for (i = 0; i < HEIGHT; i++)
 {
  for (j = 0; j < WIDTH; j++)
  {
   targetBoard[i][j] = sourceBoard[i][j];
  }
 }
}
 
void InitializeTheMaze(int Board[HEIGHT][WIDTH])
{
 int TmpBoard[HEIGHT][WIDTH] = {
  { WALL , WALL , START, WALL, WALL , WALL , WALL , WALL , WALL  },
  { WALL , PATH , PATH , PATH, PATH , PATH , PATH , PATH , WALL  },
  { WALL , PATH , WALL , WALL, WALL , PATH , WALL , WALL , WALL  },
  { WALL , PATH , WALL , PATH, WALL , PATH , PATH , PATH , WALL  },
  { WALL , WALL , WALL , PATH, WALL , PATH , WALL , PATH , WALL  },
  { WALL , PATH , WALL , PATH, PATH , PATH , PATH , PATH , WALL  },
  { WALL , PATH , WALL , WALL, WALL , WALL , WALL , PATH , WALL  },
  { WALL , PATH , PATH , PATH, PATH , PATH , PATH , PATH , WALL  },
  { WALL , PATH , WALL , WALL, WALL , WALL , WALL , WALL , WALL  },
  { WALL , PATH , PATH , PATH, PATH , PATH , PATH , PATH , WALL  },
  { WALL , WALL , WALL , WALL, WALL , WALL , WALL , PATH , WALL  },
  { WALL , PATH , PATH , PATH, PATH , PATH , PATH , PATH , WALL  },
  { WALL , PATH , WALL , WALL, PATH , WALL , WALL , PATH , WALL  },
  { WALL , PATH , PATH , PATH, PATH , PATH , PATH , PATH , WALL  },
  { WALL , PATH , WALL , PATH, WALL , PATH , WALL , PATH , WALL  },
  { WALL , PATH , WALL , PATH, PATH , PATH , WALL , PATH , WALL  },
  { WALL , PATH , WALL , WALL, WALL , WALL , WALL , PATH , WALL  },
  { WALL , PATH , PATH , PATH, PATH , PATH , PATH , PATH , WALL  },
  { WALL , WALL , WALL , WALL, WALL , WALL , WALL , PATH , WALL  },
  { WALL , PATH , PATH , PATH, PATH , PATH , WALL , PATH , WALL  },
  { WALL , WALL , PATH , WALL, WALL , WALL , WALL , PATH , WALL  },
  { WALL , PATH , PATH , PATH, WALL , PATH , PATH , PATH , WALL  },
  { WALL , PATH , WALL , WALL, WALL , PATH , WALL , WALL , WALL  },
  { WALL , PATH , PATH , PATH, WALL , PATH , PATH , PATH , WALL  },
  { WALL , PATH , WALL , PATH, WALL , PATH , WALL , PATH , WALL  },
  { WALL , PATH , WALL , PATH, PATH , PATH , PATH , PATH , WALL  },
  { WALL , WALL , WALL , WALL, WALL , PATH , WALL , PATH , WALL  },
  { WALL , PATH , PATH , PATH, PATH , PATH , PATH , PATH , WALL  },
  { WALL , PATH , WALL , PATH, PATH , WALL , PATH , WALL , WALL  },
  { WALL , PATH , PATH , PATH, WALL , WALL , PATH , WALL , WALL  },
  { WALL , WALL , WALL , PATH, WALL , WALL , PATH , WALL , WALL  },
  { WALL , PATH , PATH , PATH, PATH , WALL , PATH , PATH , WALL  },
  { WALL , WALL , WALL , PATH, WALL , WALL , PATH , PATH , WALL  },
  { WALL , PATH , PATH , PATH, WALL , WALL , WALL , PATH , WALL  },
  { WALL , PATH , WALL , PATH, WALL , PATH , WALL , PATH , WALL  },
  { WALL , PATH , WALL , PATH, PATH , PATH , PATH , PATH , WALL  },
  { WALL , PATH , PATH , PATH, PATH , WALL , PATH , PATH , WALL  },
  { WALL , PATH , WALL , PATH, PATH , PATH , PATH , PATH , WALL  },
  { WALL , WALL , WALL , WALL, PATH , WALL , PATH , WALL , WALL  },
  { WALL , PATH , PATH , PATH, PATH , WALL , PATH , PATH , WALL  },
  { WALL , PATH , WALL , WALL, WALL , WALL , PATH , WALL , WALL  },
  { WALL , PATH , PATH , PATH, WALL , PATH , PATH , PATH , WALL  },
  { WALL , PATH , WALL , WALL, WALL , WALL , PATH , WALL , WALL  },
  { WALL , PATH , PATH , PATH, WALL , PATH , PATH , PATH , WALL  },
  { WALL , PATH , WALL , PATH, WALL , PATH , WALL , PATH , WALL  },
  { WALL , PATH , WALL , PATH, PATH , PATH , PATH , PATH , WALL  },
  { WALL , WALL , WALL , WALL, WALL , WALL , WALL , PATH , WALL  },
  { WALL , PATH , PATH , PATH, PATH , PATH , PATH , PATH , WALL  },
  { WALL , PATH , PATH , WALL, WALL , WALL , PATH , PATH , WALL  },
  { WALL , END  , WALL , WALL, WALL , WALL , WALL , WALL , WALL  }
 };
 
 CopyBoard(Board, TmpBoard);
}
 
int main()
{
 int Board[HEIGHT][WIDTH];
 int Steps;
 
 InitializeTheMaze(Board);
 
 printf("* Start:\n\n");
 ShowBoard(Board);
 
 printf("* Program Answer:\n\n");
 Steps = SolveMaze(Board);
 if (Steps != -1) // Path found
 {
  printf("Number of steps: %d\n-----------------------\n", Steps);
  ShowBoard(Board);
 }
 else
 {
  printf("Maze cannot be solved! :(\n\n");
 }
}

בהצלחה!

.......................................................

פתרון שלי:

גרסה ראשונה של התוכנית:
(הקוד זמין גם כאן)

// Solve The Maze
// V0.0.2
//
// Date: 2018.06.21
// (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/ )
 
#include <stdio.h>
#include <time.h>
 
#define HEIGHT   50
#define WIDTH    9
 
#define WALL     -1
#define PATH     0
#define START    83  // 'S'
#define END      69  // 'E'
#define ARROW    176
 
#define UP       30
#define DOWN     40
#define RIGHT    50
#define LEFT     60
 
#define true 1
#define false 0
typedef int Boolean;
 
struct Point {
   int Row;
   int Column;
};
 
int SolveMaze(int Maze[HEIGHT][WIDTH]);
struct Point FindStartingPoint(int Maze[HEIGHT][WIDTH]);
struct Point FindStartingPathPoint(int Maze[HEIGHT][WIDTH]);
int SolveMazeREC(int Maze[HEIGHT][WIDTH], int h, int w, Boolean saveChanges);
void ShowBoard(int Board[HEIGHT][WIDTH]);
void CopyBoard(int targetBoard[HEIGHT][WIDTH], int sourceBoard[HEIGHT][WIDTH]);
 
// This function try to solve the maze with minimum steps.
//
// If succeeded - fill the given board with 'ARROW' in the path that is found,
//      and return the number of steps.
// If failed - return -1
int SolveMaze(int Maze[HEIGHT][WIDTH])
{
 int h, w;
 int steps = 2;
 int lowestSteps = -1;
 int lowestStepsSide = DOWN;
 int NewMaze[HEIGHT][WIDTH];
 int tmp;
 struct Point startingPathPoint;
 struct Point startingPoint;
 
 
 // Search start position
 startingPathPoint = FindStartingPathPoint(Maze);
 startingPoint = FindStartingPoint(Maze);
 h = startingPathPoint.Row;
 w = startingPathPoint.Column;
 
 // So the START position will not bother us
 Maze[startingPoint.Row][startingPoint.Column] = ARROW;
 
 Maze[h][w] = ARROW;
 
 // UP
 if (Maze[h-1][w] != WALL && Maze[h-1][w] != ARROW)
 {
  CopyBoard(NewMaze, Maze);
  tmp = SolveMazeREC(NewMaze, h-1, w, false, NULL);
  if (tmp != -1)
   if (tmp < lowestSteps || lowestSteps == -1)
   {
    lowestSteps = tmp;
    lowestStepsSide = UP;
   } 
 }
 
 // DOWN
 if (Maze[h+1][w] != WALL && Maze[h+1][w] != ARROW)
 {
  CopyBoard(NewMaze, Maze);
  tmp = SolveMazeREC(NewMaze, h+1, w, false, NULL);
  if (tmp != -1)
   if (tmp < lowestSteps || lowestSteps == -1)
   {
    lowestSteps = tmp;
    lowestStepsSide = DOWN;
   }
 }
 
 // RIGHT
 if (Maze[h][w+1] != WALL && Maze[h][w+1] != ARROW)
 {
  CopyBoard(NewMaze, Maze);
  tmp = SolveMazeREC(NewMaze, h, w+1, false, NULL);
  if (tmp != -1)
   if (tmp < lowestSteps || lowestSteps == -1)
   {
    lowestSteps = tmp;
    lowestStepsSide = RIGHT;
   }
 }
 
 // LEFT
 if (Maze[h][w-1] != WALL && Maze[h][w-1] != ARROW)
 {
  CopyBoard(NewMaze, Maze);
  tmp = SolveMazeREC(NewMaze, h, w-1, false, NULL);
  if (tmp != -1)
   if (tmp < lowestSteps || lowestSteps == -1)
   {
    lowestSteps = tmp;
    lowestStepsSide = LEFT;
   }
 }
 
 
 // (If all directions are blocked, lowestSteps = -1)
 if (lowestSteps == -1)
 {
  // Reset the START position // (We dont realy need this here)
  Maze[startingPoint.Row][startingPoint.Column] = START;
 
  return -1;
 }
 else
 {
  switch(lowestStepsSide)
  {
   case UP  :
    SolveMazeREC(NewMaze, h-1, w, true, Maze);
    break;
 
   case DOWN  :
    SolveMazeREC(NewMaze, h+1, w, true, Maze);
    break;
 
   case RIGHT :
    SolveMazeREC(NewMaze, h, w+1, true, Maze);
    break;
 
   case LEFT :
    SolveMazeREC(NewMaze, h, w-1, true, Maze);
    break;
  }
 
  // Reset the START position
  Maze[startingPoint.Row][startingPoint.Column] = START;
  return steps + lowestSteps;
 }
}
 
struct Point FindStartingPoint(int Maze[HEIGHT][WIDTH])
{
 int startRow;
 int startColumn;
 struct Point StartingPoint;
 for (startRow = 0; startRow < HEIGHT; startRow++)
 {
  for (startColumn = 0; startColumn < WIDTH; startColumn++)
  {
   if (Maze[startRow][startColumn] == START)
   {
    StartingPoint.Column = startColumn;
    StartingPoint.Row = startRow;
    return StartingPoint;
   }
  }
 }
 
 printf("Error in  FindStartingPoint\n");
 return StartingPoint;
}
 
struct Point FindStartingPathPoint(int Maze[HEIGHT][WIDTH])
{
 struct Point StartingPathPoint;
 StartingPathPoint = FindStartingPoint(Maze);
 
 if (Maze[StartingPathPoint.Row + 1][StartingPathPoint.Column] == PATH)
 {
  StartingPathPoint.Row += 1;
  return StartingPathPoint;
 } 
 else if (Maze[StartingPathPoint.Row - 1][StartingPathPoint.Column] == PATH)
 {
  StartingPathPoint.Row -= 1;
  return StartingPathPoint;
 }
 else if (Maze[StartingPathPoint.Row][StartingPathPoint.Column + 1] == PATH)
 {
  StartingPathPoint.Column += 1;
  return StartingPathPoint;
 }
 else if (Maze[StartingPathPoint.Row][StartingPathPoint.Column - 1] == PATH)
 {
  StartingPathPoint.Column -= 1;
  return StartingPathPoint;
 }
 else
 {
  printf("Error in  FindStartingPathPoint\n");
  return StartingPathPoint;
 }
}
 
 
 
int SolveMazeREC(int Maze[HEIGHT][WIDTH], int h, int w, Boolean saveChanges, int MainMaze[HEIGHT][WIDTH])
{
 int lowestSteps = -1;
 int NewMaze[HEIGHT][WIDTH];
 int lowestStepsSide = DOWN;
 int tmp;
 
 // -- END
 if (Maze[h][w] == END)
  return 1;
 
 Maze[h][w] = ARROW;
 if (saveChanges == true)
 {
  MainMaze[h][w] = ARROW;
 }
 
 // UP
 if (Maze[h-1][w] != WALL && Maze[h-1][w] != ARROW)
 {
  CopyBoard(NewMaze, Maze);
  tmp = SolveMazeREC(NewMaze, h-1, w, false, NULL);
  if (tmp != -1)
   if (tmp < lowestSteps || lowestSteps == -1)
   {
    lowestSteps = tmp;
    lowestStepsSide = UP;
   }
 }
 
 // DOWN
 if (Maze[h+1][w] != WALL && Maze[h+1][w] != ARROW)
 {
  CopyBoard(NewMaze, Maze);
  tmp = SolveMazeREC(NewMaze, h+1, w, false, NULL);
  if (tmp != -1)
   if (tmp < lowestSteps || lowestSteps == -1)
   {
    lowestSteps = tmp;
    lowestStepsSide = DOWN;
   }
 }
 
 // RIGHT
 if (Maze[h][w+1] != WALL && Maze[h][w+1] != ARROW)
 {
  CopyBoard(NewMaze, Maze);
  tmp = SolveMazeREC(NewMaze, h, w+1, false, NULL);
  if (tmp != -1)
   if (tmp < lowestSteps || lowestSteps == -1)
   {
    lowestSteps = tmp;
    lowestStepsSide = RIGHT;
   }
 }
 
 // LEFT
 if (Maze[h][w-1] != WALL && Maze[h][w-1] != ARROW)
 {
  CopyBoard(NewMaze, Maze);
  tmp = SolveMazeREC(NewMaze, h, w-1, false, NULL);
  if (tmp != -1)
   if (tmp < lowestSteps || lowestSteps == -1)
   {
    lowestSteps = tmp;
    lowestStepsSide = LEFT;
   }
 }
 
 
 Maze[h][w] = PATH;
 if (saveChanges == true)
 {
  if (lowestSteps != -1)
  {
   switch(lowestStepsSide)
   {
    case UP  :
     SolveMazeREC(NewMaze, h-1, w, true, MainMaze);
     break;
 
    case DOWN  :
     SolveMazeREC(NewMaze, h+1, w, true, MainMaze);
     break;
 
    case RIGHT :
     SolveMazeREC(NewMaze, h, w+1, true, MainMaze);
     break;
 
    case LEFT :
     SolveMazeREC(NewMaze, h, w-1, true, MainMaze);
     break;
   }
  }
 }
 
 // (If all directions are blocked, lowestSteps = -1)
 if (lowestSteps == -1)
 {
  return -1;
 }
 else
 {
  return 1 + lowestSteps;
 }
}
 
void ShowBoard(int Board[HEIGHT][WIDTH])
{
 int row;
 int col;
 
 printf("Full maze:\n\n\n");
 
 for (row = 0; row < HEIGHT; row++)    // Loop through every row
 {
  for (col = 0; col < WIDTH; col++) // And every column
  {
   switch(Board[row][col])
   {
    case WALL  :
      putchar('\xDB');
      break;
 
    case PATH  :
      putchar(' ');
      break;
 
    case ARROW :
      putchar(ARROW);
      break;
 
       case START :
      putchar(START);
      break;
 
       case END   :
      putchar(END);
      break;
 
      default    :
      putchar('?');
      break;
   }
  }
  putchar('\n');
 }
 printf("\n\n\n");
}
 
void CopyBoard(int targetBoard[HEIGHT][WIDTH], int sourceBoard[HEIGHT][WIDTH])
{
 int i, j;
 for (i = 0; i < HEIGHT; i++)
 {
  for (j = 0; j < WIDTH; j++)
  {
   targetBoard[i][j] = sourceBoard[i][j];
  }
 }
}
 
void InitializeTheMaze(int Board[HEIGHT][WIDTH])
{
 int TmpBoard[HEIGHT][WIDTH] = {
  { WALL , WALL , START, WALL, WALL , WALL , WALL , WALL , WALL  },
  { WALL , PATH , PATH , PATH, PATH , PATH , PATH , PATH , WALL  },
  { WALL , PATH , WALL , WALL, WALL , PATH , WALL , WALL , WALL  },
  { WALL , PATH , WALL , PATH, WALL , PATH , PATH , PATH , WALL  },
  { WALL , WALL , WALL , PATH, WALL , PATH , WALL , PATH , WALL  },
  { WALL , PATH , WALL , PATH, PATH , PATH , PATH , PATH , WALL  },
  { WALL , PATH , WALL , WALL, WALL , WALL , WALL , PATH , WALL  },
  { WALL , PATH , PATH , PATH, PATH , PATH , PATH , PATH , WALL  },
  { WALL , PATH , WALL , WALL, WALL , WALL , WALL , WALL , WALL  },
  { WALL , PATH , PATH , PATH, PATH , PATH , PATH , PATH , WALL  },
  { WALL , WALL , WALL , WALL, WALL , WALL , WALL , PATH , WALL  },
  { WALL , PATH , PATH , PATH, PATH , PATH , PATH , PATH , WALL  },
  { WALL , PATH , WALL , WALL, PATH , WALL , WALL , PATH , WALL  },
  { WALL , PATH , PATH , PATH, PATH , PATH , PATH , PATH , WALL  },
  { WALL , PATH , WALL , PATH, WALL , PATH , WALL , PATH , WALL  },
  { WALL , PATH , WALL , PATH, PATH , PATH , WALL , PATH , WALL  },
  { WALL , PATH , WALL , WALL, WALL , WALL , WALL , PATH , WALL  },
  { WALL , PATH , PATH , PATH, PATH , PATH , PATH , PATH , WALL  },
  { WALL , WALL , WALL , WALL, WALL , WALL , WALL , PATH , WALL  },
  { WALL , PATH , PATH , PATH, PATH , PATH , WALL , PATH , WALL  },
  { WALL , WALL , PATH , WALL, WALL , WALL , WALL , PATH , WALL  },
  { WALL , PATH , PATH , PATH, WALL , PATH , PATH , PATH , WALL  },
  { WALL , PATH , WALL , WALL, WALL , PATH , WALL , WALL , WALL  },
  { WALL , PATH , PATH , PATH, WALL , PATH , PATH , PATH , WALL  },
  { WALL , PATH , WALL , PATH, WALL , PATH , WALL , PATH , WALL  },
  { WALL , PATH , WALL , PATH, PATH , PATH , PATH , PATH , WALL  },
  { WALL , WALL , WALL , WALL, WALL , PATH , WALL , PATH , WALL  },
  { WALL , PATH , PATH , PATH, PATH , PATH , PATH , PATH , WALL  },
  { WALL , PATH , WALL , PATH, PATH , WALL , PATH , WALL , WALL  },
  { WALL , PATH , PATH , PATH, WALL , WALL , PATH , WALL , WALL  },
  { WALL , WALL , WALL , PATH, WALL , WALL , PATH , WALL , WALL  },
  { WALL , PATH , PATH , PATH, PATH , WALL , PATH , PATH , WALL  },
  { WALL , WALL , WALL , PATH, WALL , WALL , PATH , PATH , WALL  },
  { WALL , PATH , PATH , PATH, WALL , WALL , WALL , PATH , WALL  },
  { WALL , PATH , WALL , PATH, WALL , PATH , WALL , PATH , WALL  },
  { WALL , PATH , WALL , PATH, PATH , PATH , PATH , PATH , WALL  },
  { WALL , PATH , PATH , PATH, PATH , WALL , PATH , PATH , WALL  },
  { WALL , PATH , WALL , PATH, PATH , PATH , PATH , PATH , WALL  },
  { WALL , WALL , WALL , WALL, PATH , WALL , PATH , WALL , WALL  },
  { WALL , PATH , PATH , PATH, PATH , WALL , PATH , PATH , WALL  },
  { WALL , PATH , WALL , WALL, WALL , WALL , PATH , WALL , WALL  },
  { WALL , PATH , PATH , PATH, WALL , PATH , PATH , PATH , WALL  },
  { WALL , PATH , WALL , WALL, WALL , WALL , PATH , WALL , WALL  },
  { WALL , PATH , PATH , PATH, WALL , PATH , PATH , PATH , WALL  },
  { WALL , PATH , WALL , PATH, WALL , PATH , WALL , PATH , WALL  },
  { WALL , PATH , WALL , PATH, PATH , PATH , PATH , PATH , WALL  },
  { WALL , WALL , WALL , WALL, WALL , WALL , WALL , PATH , WALL  },
  { WALL , PATH , PATH , PATH, PATH , PATH , PATH , PATH , WALL  },
  { WALL , PATH , PATH , WALL, WALL , WALL , PATH , PATH , WALL  },
  { WALL , END  , WALL , WALL, WALL , WALL , WALL , WALL , WALL  },
 };
 
 CopyBoard(Board, TmpBoard);
}
 
int main()
{
 int Board[HEIGHT][WIDTH];
 int Steps;
 clock_t begin, end;
 double time_spent;
 
 InitializeTheMaze(Board);
 
 printf("* Start:\n\n");
 ShowBoard(Board);
 
 printf("* Program Answer:\n\n");
 
 begin = clock();
 Steps = SolveMaze(Board);
 end = clock();
 time_spent = (double)(end - begin) / CLOCKS_PER_SEC;
 
 if (Steps != -1) // Path found
 {
  printf("Number of steps: %d\n-----------------------\n", Steps);
  ShowBoard(Board);
 }
 else
 {
  printf("Maze cannot be solved! :(\n\n");
 }
 
 printf("Time:  %lf Seconds\n", time_spent);
 getchar();
}

הקוד הזה עובר על כל האפשרויות ובודק מי היא הקצרה מכולן.
הבעיה היא שלקוד לוקח 121.126 שניות לפתור את המבוך הנוכחי. איטי מאוד מאוד.

למעשה הרבה מאוד מזמן הריצה מתבזבז על הפונקציה CopyBoard.
נוכל לשפר אותה אם נשתמש בפונקציה memcpy להעתקת מערכים, עבורה נוסיף את הספרייה <memory.h>.

כך תראה הפונקציה המשופרת:

void CopyBoard(int targetBoard[HEIGHT][WIDTH], int sourceBoard[HEIGHT][WIDTH])
{
 memcpy(targetBoard, sourceBoard, WIDTH * HEIGHT * sizeof(int));
}

לאחר השינוי הזה לקוד לוקח 12.849 שניות לפתור את המבוך הנוכחי. טוב יותר אבל עדיין לא מושלם.

עד עכשיו הקוד לא עשה שום דבר מתוחכם חוץ מלרוץ על כל האפשרויות, עכשיו ננסה להיות חכמים יותר.
נעשה שימוש במערך עזר גלובלי:

int MinStepsToEachPositionInMaze[HEIGHT][WIDTH];

אשר נועד להחזיק את מספר הצעדים של הדרך הקצרה ביותר שנמצאה (עד לאותו רגע שקראו לו) להגיע לכל אחת מהמשבצות במבוך.
לדוגמה:

אם באחת מהדרכים שניסינו הייתה דרך שהגיעה למשבצת [Maze[3][5 ב-7 צעדים,
האיבר [MinStepsToEachPositionInMaze[3][5 יכיל את המספר 7.

לאחר מכן:

אם בניסיון אחר אנחנו מגיעים לאותה משבצת ביותר צעדים -
אנחנו יכולים לדעת שהנתיב הנוכחי הוא לא המהיר ביותר ולכן אין טעם להמשיך בו.

אם בניסיון אחר אנחנו מגיעים לאותה משבצת באותו מספר צעדים -
אנחנו יכולים לדעת שהנתיב הנוכחי לא יהיה יותר טוב מנתיב שכבר נבדק בעבר, ולכן אין טעם להמשיך בו.

אם בניסיון אחר אנחנו מגיעים לאותה משבצת בפחות צעדים -
נעדכן את המערך MinStepsToEachPositionInMaze.

כעת נראה את הקוד החדש:
(הקוד זמין גם כאן)

// Solve The Maze
// V0.1.2
//
// Date: 2018.06.21
// (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/ )
 
 
#include <stdio.h>
#include <memory.h>
#include <time.h>
 
#define HEIGHT   50
#define WIDTH    9
 
#define WALL     -1
#define PATH     0
#define START    83  // 'S'
#define END      69  // 'E'
#define ARROW    176
 
#define UP       30
#define DOWN     40
#define RIGHT    50
#define LEFT     60
 
#define true 1
#define false 0
typedef int Boolean;
 
struct Point {
   int Row;
   int Column;
};
 
int SolveMaze(int Maze[HEIGHT][WIDTH]);
struct Point FindStartingPoint(int Maze[HEIGHT][WIDTH]);
struct Point FindStartingPathPoint(int Maze[HEIGHT][WIDTH]);
int SolveMazeREC(int Maze[HEIGHT][WIDTH], int h, int w, Boolean saveChanges);
void ShowBoard(int Board[HEIGHT][WIDTH]);
void CopyBoard(int targetBoard[HEIGHT][WIDTH], int sourceBoard[HEIGHT][WIDTH]);
void InitMinStepsInMazeArray();
 
int MinStepsToEachPositionInMaze[HEIGHT][WIDTH]; // Fast the code...
 
 
// This function try to solve the maze with minimum steps.
//
// If succeeded - fill the given board with 'ARROW' in the path that is found,
//      and return the number of steps.
// If failed - return -1
int SolveMaze(int Maze[HEIGHT][WIDTH])
{
 int h, w;
 int steps = 2;
 int lowestSteps = -1;
 int lowestStepsSide = DOWN;
 int NewMaze[HEIGHT][WIDTH];
 int tmp;
 struct Point startingPathPoint;
 struct Point startingPoint;
 
 InitMinStepsInMazeArray();
 
 // Search start position
 startingPathPoint = FindStartingPathPoint(Maze);
 startingPoint = FindStartingPoint(Maze);
 h = startingPathPoint.Row;
 w = startingPathPoint.Column;
 
 MinStepsToEachPositionInMaze[h][w] = steps-1;
 
 // So the START position will not bother us
 Maze[startingPoint.Row][startingPoint.Column] = ARROW;
 
 Maze[h][w] = ARROW;
 
 // UP
 if (Maze[h-1][w] != WALL && Maze[h-1][w] != ARROW)
 {
  CopyBoard(NewMaze, Maze);
  tmp = SolveMazeREC(NewMaze, h-1, w, steps, false, NULL);
  if (tmp != -1)
   if (tmp < lowestSteps || lowestSteps == -1)
   {
    lowestSteps = tmp;
    lowestStepsSide = UP;
   } 
 }
 
 // DOWN
 if (Maze[h+1][w] != WALL && Maze[h+1][w] != ARROW)
 {
  CopyBoard(NewMaze, Maze);
  tmp = SolveMazeREC(NewMaze, h+1, w, steps, false, NULL);
  if (tmp != -1)
   if (tmp < lowestSteps || lowestSteps == -1)
   {
    lowestSteps = tmp;
    lowestStepsSide = DOWN;
   }
 }
 
 // RIGHT
 if (Maze[h][w+1] != WALL && Maze[h][w+1] != ARROW)
 {
  CopyBoard(NewMaze, Maze);
  tmp = SolveMazeREC(NewMaze, h, w+1, steps, false, NULL);
  if (tmp != -1)
   if (tmp < lowestSteps || lowestSteps == -1)
   {
    lowestSteps = tmp;
    lowestStepsSide = RIGHT;
   }
 }
 
 // LEFT
 if (Maze[h][w-1] != WALL && Maze[h][w-1] != ARROW)
 {
  CopyBoard(NewMaze, Maze);
  tmp = SolveMazeREC(NewMaze, h, w-1, steps, false, NULL);
  if (tmp != -1)
   if (tmp < lowestSteps || lowestSteps == -1)
   {
    lowestSteps = tmp;
    lowestStepsSide = LEFT;
   }
 }
 
 // (If all directions are blocked, lowestSteps = -1)
 if (lowestSteps == -1)
 {
  // Reset the START position // (We dont realy need this here)
  Maze[startingPoint.Row][startingPoint.Column] = START;
 
  return -1;
 }
 else
 {
  InitMinStepsInMazeArray();
  switch(lowestStepsSide)
  {
   case UP  :
    SolveMazeREC(NewMaze, h-1, w, steps, true, Maze);
    break;
 
   case DOWN  :
    SolveMazeREC(NewMaze, h+1, w, steps, true, Maze);
    break;
 
   case RIGHT :
    SolveMazeREC(NewMaze, h, w+1, steps, true, Maze);
    break;
 
   case LEFT :
    SolveMazeREC(NewMaze, h, w-1, steps, true, Maze);
    break;
  }
 
  // Reset the START position
  Maze[startingPoint.Row][startingPoint.Column] = START;
  return steps + lowestSteps;
 }
}
 
struct Point FindStartingPoint(int Maze[HEIGHT][WIDTH])
{
 int startRow;
 int startColumn;
 struct Point StartingPoint;
 for (startRow = 0; startRow < HEIGHT; startRow++)
 {
  for (startColumn = 0; startColumn < WIDTH; startColumn++)
  {
   if (Maze[startRow][startColumn] == START)
   {
    StartingPoint.Column = startColumn;
    StartingPoint.Row = startRow;
    return StartingPoint;
   }
  }
 }
 
 printf("Error in  FindStartingPoint\n");
 return StartingPoint;
}
 
struct Point FindStartingPathPoint(int Maze[HEIGHT][WIDTH])
{
 struct Point StartingPathPoint;
 StartingPathPoint = FindStartingPoint(Maze);
 
 if (Maze[StartingPathPoint.Row + 1][StartingPathPoint.Column] == PATH)
 {
  StartingPathPoint.Row += 1;
  return StartingPathPoint;
 } 
 else if (Maze[StartingPathPoint.Row - 1][StartingPathPoint.Column] == PATH)
 {
  StartingPathPoint.Row -= 1;
  return StartingPathPoint;
 }
 else if (Maze[StartingPathPoint.Row][StartingPathPoint.Column + 1] == PATH)
 {
  StartingPathPoint.Column += 1;
  return StartingPathPoint;
 }
 else if (Maze[StartingPathPoint.Row][StartingPathPoint.Column - 1] == PATH)
 {
  StartingPathPoint.Column -= 1;
  return StartingPathPoint;
 }
 else
 {
  printf("Error in  FindStartingPathPoint\n");
  return StartingPathPoint;
 }
}
 
int SolveMazeREC(int Maze[HEIGHT][WIDTH], int h, int w, int stepsUntilNow,
     Boolean saveChanges, int MainMaze[HEIGHT][WIDTH])
{
 int lowestSteps = -1;
 int NewMaze[HEIGHT][WIDTH];
 int lowestStepsSide = DOWN;
 int tmp;
 
 if (MinStepsToEachPositionInMaze[h][w] <= stepsUntilNow)
 {
  return -1;
 }
 else
 {
  MinStepsToEachPositionInMaze[h][w] = stepsUntilNow;
 }
 
 // -- END
 if (Maze[h][w] == END)
  return 1;
 
 Maze[h][w] = ARROW;
 if (saveChanges == true)
 {
  MainMaze[h][w] = ARROW;
 }
 
 // UP
 if (Maze[h-1][w] != WALL && Maze[h-1][w] != ARROW)
 {
  CopyBoard(NewMaze, Maze);
  tmp = SolveMazeREC(NewMaze, h-1, w, stepsUntilNow+1, false, NULL);
  if (tmp != -1)
   if (tmp < lowestSteps || lowestSteps == -1)
   {
    lowestSteps = tmp;
    lowestStepsSide = UP;
   }
 }
 
 // DOWN
 if (Maze[h+1][w] != WALL && Maze[h+1][w] != ARROW)
 {
  CopyBoard(NewMaze, Maze);
  tmp = SolveMazeREC(NewMaze, h+1, w, stepsUntilNow+1, false, NULL);
  if (tmp != -1)
   if (tmp < lowestSteps || lowestSteps == -1)
   {
    lowestSteps = tmp;
    lowestStepsSide = DOWN;
   }
 }
 
 // RIGHT
 if (Maze[h][w+1] != WALL && Maze[h][w+1] != ARROW)
 {
  CopyBoard(NewMaze, Maze);
  tmp = SolveMazeREC(NewMaze, h, w+1, stepsUntilNow+1, false, NULL);
  if (tmp != -1)
   if (tmp < lowestSteps || lowestSteps == -1)
   {
    lowestSteps = tmp;
    lowestStepsSide = RIGHT;
   }
 }
 
 // LEFT
 if (Maze[h][w-1] != WALL && Maze[h][w-1] != ARROW)
 {
  CopyBoard(NewMaze, Maze);
  tmp = SolveMazeREC(NewMaze, h, w-1, stepsUntilNow+1, false, NULL);
  if (tmp != -1)
   if (tmp < lowestSteps || lowestSteps == -1)
   {
    lowestSteps = tmp;
    lowestStepsSide = LEFT;
   }
 }
 
 Maze[h][w] = PATH;
 if (saveChanges == true)
 {
  if (lowestSteps != -1)
  {
   InitMinStepsInMazeArray();
   switch(lowestStepsSide)
   {
    case UP  :
     SolveMazeREC(NewMaze, h-1, w, stepsUntilNow+1, true, MainMaze);
     break;
 
    case DOWN  :
     SolveMazeREC(NewMaze, h+1, w, stepsUntilNow+1, true, MainMaze);
     break;
 
    case RIGHT :
     SolveMazeREC(NewMaze, h, w+1, stepsUntilNow+1, true, MainMaze);
     break;
 
    case LEFT :
     SolveMazeREC(NewMaze, h, w-1, stepsUntilNow+1, true, MainMaze);
     break;
   }
  }
 }
 
 
 // (If all directions are blocked, lowestSteps = -1)
 if (lowestSteps == -1)
 {
  // MinStepsToEachPositionInMaze[h][w] = -1; // maybe give us bag?
  return -1;
 }
 else
 {
  return 1 + lowestSteps;
 }
}
 
void InitMinStepsInMazeArray()
{
 int i, j;
 for (i = 0; i < HEIGHT; i++)
 {
  for (j = 0; j < WIDTH; j++)
  {
   MinStepsToEachPositionInMaze[i][j] = 100000; // Any number greater than number of positions in maze
  }
 }
}
 
void ShowBoard(int Board[HEIGHT][WIDTH])
{
 int row;
 int col;
 
 printf("Full maze:\n\n\n");
 
 for (row = 0; row < HEIGHT; row++)    // Loop through every row
 {
  for (col = 0; col < WIDTH; col++) // And every column
  {
   switch(Board[row][col])
   {
    case WALL  :
      putchar('\xDB');
      break;
 
    case PATH  :
      putchar(' ');
      break;
 
    case ARROW :
      putchar(ARROW);
      break;
    
    case START :
      putchar(START);
      break;
    
    case END   :
      putchar(END);
      break;
    
    default    :
      putchar('?');
      break;
   }
  }
  putchar('\n');
 }
 printf("\n\n\n");
}
 
void CopyBoard(int targetBoard[HEIGHT][WIDTH], int sourceBoard[HEIGHT][WIDTH])
{
 //int i, j;
 //for (i = 0; i < HEIGHT; i++)
 //{
 // for (j = 0; j < WIDTH; j++)
 // {
 //  targetBoard[i][j] = sourceBoard[i][j];
 // }
 //}
 
 // Fast copy:
 memcpy(targetBoard, sourceBoard, WIDTH * HEIGHT * sizeof(int));
}
 
void InitializeTheMaze(int Board[HEIGHT][WIDTH])
{
 // Maze Option A:
 // #define HEIGHT   50
 // #define WIDTH    9
 int TmpBoard[HEIGHT][WIDTH] = {
  { WALL , WALL , START, WALL, WALL , WALL , WALL , WALL , WALL  },
  { WALL , PATH , PATH , PATH, PATH , PATH , PATH , PATH , WALL  },
  { WALL , PATH , WALL , WALL, WALL , PATH , WALL , WALL , WALL  },
  { WALL , PATH , WALL , PATH, WALL , PATH , PATH , PATH , WALL  },
  { WALL , WALL , WALL , PATH, WALL , PATH , WALL , PATH , WALL  },
  { WALL , PATH , WALL , PATH, PATH , PATH , PATH , PATH , WALL  },
  { WALL , PATH , WALL , WALL, WALL , WALL , WALL , PATH , WALL  },
  { WALL , PATH , PATH , PATH, PATH , PATH , PATH , PATH , WALL  },
  { WALL , PATH , WALL , WALL, WALL , WALL , WALL , WALL , WALL  },
  { WALL , PATH , PATH , PATH, PATH , PATH , PATH , PATH , WALL  },
  { WALL , WALL , WALL , WALL, WALL , WALL , WALL , PATH , WALL  },
  { WALL , PATH , PATH , PATH, PATH , PATH , PATH , PATH , WALL  },
  { WALL , PATH , WALL , WALL, PATH , WALL , WALL , PATH , WALL  },
  { WALL , PATH , PATH , PATH, PATH , PATH , PATH , PATH , WALL  },
  { WALL , PATH , WALL , PATH, WALL , PATH , WALL , PATH , WALL  },
  { WALL , PATH , WALL , PATH, PATH , PATH , WALL , PATH , WALL  },
  { WALL , PATH , WALL , WALL, WALL , WALL , WALL , PATH , WALL  },
  { WALL , PATH , PATH , PATH, PATH , PATH , PATH , PATH , WALL  },
  { WALL , WALL , WALL , WALL, WALL , WALL , WALL , PATH , WALL  },
  { WALL , PATH , PATH , PATH, PATH , PATH , WALL , PATH , WALL  },
  { WALL , WALL , PATH , WALL, WALL , WALL , WALL , PATH , WALL  },
  { WALL , PATH , PATH , PATH, WALL , PATH , PATH , PATH , WALL  },
  { WALL , PATH , WALL , WALL, WALL , PATH , WALL , WALL , WALL  },
  { WALL , PATH , PATH , PATH, WALL , PATH , PATH , PATH , WALL  },
  { WALL , PATH , WALL , PATH, WALL , PATH , WALL , PATH , WALL  },
  { WALL , PATH , WALL , PATH, PATH , PATH , PATH , PATH , WALL  },
  { WALL , WALL , WALL , WALL, WALL , PATH , WALL , PATH , WALL  },
  { WALL , PATH , PATH , PATH, PATH , PATH , PATH , PATH , WALL  },
  { WALL , PATH , WALL , PATH, PATH , WALL , PATH , WALL , WALL  },
  { WALL , PATH , PATH , PATH, WALL , WALL , PATH , WALL , WALL  },
  { WALL , WALL , WALL , PATH, WALL , WALL , PATH , WALL , WALL  },
  { WALL , PATH , PATH , PATH, PATH , WALL , PATH , PATH , WALL  },
  { WALL , WALL , WALL , PATH, WALL , WALL , PATH , PATH , WALL  },
  { WALL , PATH , PATH , PATH, WALL , WALL , WALL , PATH , WALL  },
  { WALL , PATH , WALL , PATH, WALL , PATH , WALL , PATH , WALL  },
  { WALL , PATH , WALL , PATH, PATH , PATH , PATH , PATH , WALL  },
  { WALL , PATH , PATH , PATH, PATH , WALL , PATH , PATH , WALL  },
  { WALL , PATH , WALL , PATH, PATH , PATH , PATH , PATH , WALL  },
  { WALL , WALL , WALL , WALL, PATH , WALL , PATH , WALL , WALL  },
  { WALL , PATH , PATH , PATH, PATH , WALL , PATH , PATH , WALL  },
  { WALL , PATH , WALL , WALL, WALL , WALL , PATH , WALL , WALL  },
  { WALL , PATH , PATH , PATH, WALL , PATH , PATH , PATH , WALL  },
  { WALL , PATH , WALL , WALL, WALL , WALL , PATH , WALL , WALL  },
  { WALL , PATH , PATH , PATH, WALL , PATH , PATH , PATH , WALL  },
  { WALL , PATH , WALL , PATH, WALL , PATH , WALL , PATH , WALL  },
  { WALL , PATH , WALL , PATH, PATH , PATH , PATH , PATH , WALL  },
  { WALL , WALL , WALL , WALL, WALL , WALL , WALL , PATH , WALL  },
  { WALL , PATH , PATH , PATH, PATH , PATH , PATH , PATH , WALL  },
  { WALL , PATH , PATH , WALL, WALL , WALL , PATH , PATH , WALL  },
  { WALL , END  , WALL , WALL, WALL , WALL , WALL , WALL , WALL  },
 };
 
 
 
 // Maze Option B:
 //// #define HEIGHT   9
 //// #define WIDTH    9
 //int TmpBoard[HEIGHT][WIDTH] = {
 // { WALL , WALL , START, WALL, WALL , WALL , WALL , WALL , WALL  },
 // { WALL , PATH , PATH , PATH, PATH , PATH , PATH , PATH , WALL  },
 // { WALL , PATH , WALL , WALL, WALL , PATH , WALL , WALL , WALL  },
 // { WALL , PATH , WALL , PATH, WALL , PATH , PATH , PATH , WALL  },
 // { WALL , WALL , WALL , PATH, WALL , PATH , WALL , PATH , WALL  },
 // { WALL , PATH , WALL , PATH, PATH , PATH , PATH , PATH , WALL  },
 // { WALL , PATH , WALL , WALL, WALL , WALL , WALL , PATH , WALL  },
 // { WALL , PATH , PATH , PATH, PATH , PATH , PATH , PATH , WALL  },
 // { WALL , END  , WALL , WALL, WALL , WALL , WALL , WALL , WALL  },
 //};
 
 
 // Maze Option C:
 //// #define HEIGHT   19
 //// #define WIDTH    9
 //int TmpBoard[HEIGHT][WIDTH] = {
 // { WALL , WALL , START, WALL, WALL , WALL , WALL , WALL , WALL  },
 // { WALL , PATH , PATH , PATH, PATH , PATH , PATH , PATH , WALL  },
 // { WALL , PATH , WALL , WALL, WALL , PATH , WALL , WALL , WALL  },
 // { WALL , PATH , WALL , PATH, WALL , PATH , PATH , PATH , WALL  },
 // { WALL , WALL , WALL , PATH, WALL , PATH , WALL , PATH , WALL  },
 // { WALL , PATH , WALL , PATH, PATH , PATH , PATH , PATH , WALL  },
 // { WALL , PATH , WALL , WALL, WALL , WALL , WALL , PATH , WALL  },
 // { WALL , PATH , PATH , PATH, PATH , PATH , PATH , PATH , WALL  },
 // { WALL , PATH , WALL , WALL, WALL , WALL , WALL , WALL , WALL  },
 // { WALL , PATH , PATH , PATH, PATH , PATH , PATH , PATH , WALL  },
 // { WALL , WALL , WALL , WALL, WALL , WALL , WALL , PATH , WALL  },
 // { WALL , PATH , PATH , PATH, PATH , PATH , PATH , PATH , WALL  },
 // { WALL , PATH , WALL , WALL, PATH , WALL , WALL , PATH , WALL  },
 // { WALL , PATH , PATH , PATH, PATH , PATH , PATH , PATH , WALL  },
 // { WALL , WALL , WALL , PATH, WALL , PATH , WALL , PATH , WALL  },
 // { END  , PATH , WALL , PATH, PATH , PATH , WALL , PATH , WALL  },
 // { WALL , PATH , WALL , WALL, WALL , WALL , WALL , PATH , WALL  },
 // { WALL , PATH , PATH , PATH, PATH , PATH , PATH , PATH , WALL  },
 // { WALL , WALL , WALL , WALL, WALL , WALL , WALL , WALL , WALL  },
 //};
 
 CopyBoard(Board, TmpBoard);
}
 
int main()
{
 int Board[HEIGHT][WIDTH];
 int Steps;
 clock_t begin, end;
 double time_spent;
 
 InitializeTheMaze(Board);
 
 printf("* Start:\n\n");
 ShowBoard(Board);
 
 printf("* Program Answer:\n\n");
 
 begin = clock();
 Steps = SolveMaze(Board);
 end = clock();
 time_spent = (double)(end - begin) / CLOCKS_PER_SEC;
 
 if (Steps != -1) // Path found
 {
  printf("Number of steps: %d\n-----------------------\n", Steps);
  ShowBoard(Board);
 }
 else
 {
  printf("Maze cannot be solved! :(\n\n");
 }
 
 printf("Time:  %lf Seconds\n", time_spent);
 getchar();
}

כל הכבוד! הקוד הזה פותר את אותו המבוך ב-0.004 שניות.
הצלחנו אפילו לעבור את ה-0.715 שניות שלקחו לקוד של Symbol/Skyance,

למען האמת הקוד עדיין לא מושלם, ואלו הדברים שהייתי רוצה לשפר בו:
- לעצור ריצה על נתיב ברגע שהגענו למספר צעדים גדול או שווה למספר הצעדים של הנתיב הקצר ביותר שנמצא.
(או יותר טוב: לעצור ברגע שהגענו למספר צעדים שאם נוסיף לו את "מרחק הצעדים שנותרו בקו אווירי" הוא יהיה גדול או שווה
למספר הצעדים של הנתיב הקצר ביותר שנמצא)

- הקוד הנוכחי פותר את המבוך פעמיים, פעם אחת הוא רק מחפש נתיב, ובפעם השנייה הוא גם צובע את הנתיב שנמצא.
עדיף קוד ששומר ברשימה את המידע שנאסף בחיפוש הראשון, ואז פשוט צובע את המבוך על פי הרשימה.

.........
עריכה:
הנה הקוד הסופי שעונה לשני ה"שיפורים" שרציתי להוסיף.
כלומר הוא גם "עוצר ריצה ברגע שהגענו למספר צעדים גדול או שווה למספר הצעדים של הנתיב הקצר ביותר שנמצא",
וגם "שומר ברשימה את כל המידע שנאסף בריצה הראשונה", מה שמאפשר למחוק את הריצה השנייה.
(הקוד זמין גם כאן)

// Solve The Maze
// V0.2.2
//
// Date: 2018.06.24
// (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/ )
 
 
#include <stdio.h>
#include <memory.h>
#include <time.h>
#include <stdlib.h>
 
 
#define HEIGHT   50
#define WIDTH    9
 
#define WALL     -1
#define PATH     0
#define START    83  // 'S'
#define END      69  // 'E'
#define ARROW    176
 
#define true 1
#define false 0
typedef int Boolean;
 
struct Point {
   int Row;
   int Column;
};
 
typedef struct node {
    struct Point point;
    struct node* next;
} node_t, node_p;
 
int SolveMaze(int Maze[HEIGHT][WIDTH]);
struct Point FindStartingPoint(int Maze[HEIGHT][WIDTH]);
struct Point FindStartingPathPoint(int Maze[HEIGHT][WIDTH]);
int SolveMazeREC(int Maze[HEIGHT][WIDTH], int h, int w, int stepsUntilNow, node_t** outHeadOfList);
void ShowBoard(int Board[HEIGHT][WIDTH]);
void CopyBoard(int targetBoard[HEIGHT][WIDTH], int sourceBoard[HEIGHT][WIDTH]);
void InitMinStepsInMazeArray();
struct node* CreateNewList(struct Point point);
void PrintList(struct node* head);
void FreeList(struct node* head);
void PushToList(node_t ** refEnd, struct Point point);
void PaintAllPositionsInMazeThatAppearInFinalList(struct node* headOfFinalList, int Maze[HEIGHT][WIDTH]);
 
// Global Variables
int MinStepsToEachPositionInMaze[HEIGHT][WIDTH];
int MinStepsToGoToEnd;
 
 
// This function try to solve the maze with minimum steps.
//
// If succeeded - fill the given board with 'ARROW' in the path that is found,
//      and return the number of steps.
// If failed - return -1
int SolveMaze(int Maze[HEIGHT][WIDTH])
{
 int h, w;
 int steps = 2;
 int lowestSteps = -1;
 int NewMaze[HEIGHT][WIDTH];
 int tmp;
 struct Point startingPathPoint;
 struct Point startingPoint;
 struct node* headOfFinalList;
 struct node* headOfNewList;
 
 // Init global variables
 InitMinStepsInMazeArray();
 MinStepsToGoToEnd = HEIGHT * WIDTH + 10; // Any number greater than number of positions in maze
 
 // Search start position
 startingPathPoint = FindStartingPathPoint(Maze);
 startingPoint = FindStartingPoint(Maze);
 
 // Init final positions list 
 headOfFinalList = CreateNewList(startingPathPoint);
 
 h = startingPathPoint.Row;
 w = startingPathPoint.Column;
 
 MinStepsToEachPositionInMaze[h][w] = steps-1;
 
 // So the START position will not bother us
 Maze[startingPoint.Row][startingPoint.Column] = ARROW;
 
 Maze[h][w] = ARROW;
 
 // UP
 if (Maze[h-1][w] != WALL && Maze[h-1][w] != ARROW)
 {
  CopyBoard(NewMaze, Maze);
  tmp = SolveMazeREC(NewMaze, h-1, w, steps, &headOfNewList);
  if (tmp != -1)
   if (tmp < lowestSteps || lowestSteps == -1)
   {
    lowestSteps = tmp;
    headOfFinalList->next = headOfNewList;
   } 
 }
 
 // DOWN
 if (Maze[h+1][w] != WALL && Maze[h+1][w] != ARROW)
 {
  CopyBoard(NewMaze, Maze);
  tmp = SolveMazeREC(NewMaze, h+1, w, steps, &headOfNewList);
  if (tmp != -1)
   if (tmp < lowestSteps || lowestSteps == -1)
   {
    lowestSteps = tmp;
    headOfFinalList->next = headOfNewList;
   }
 }
 
 // RIGHT
 if (Maze[h][w+1] != WALL && Maze[h][w+1] != ARROW)
 {
  CopyBoard(NewMaze, Maze);
  tmp = SolveMazeREC(NewMaze, h, w+1, steps, &headOfNewList);
  if (tmp != -1)
   if (tmp < lowestSteps || lowestSteps == -1)
   {
    lowestSteps = tmp;
    headOfFinalList->next = headOfNewList;
   }
 }
 
 // LEFT
 if (Maze[h][w-1] != WALL && Maze[h][w-1] != ARROW)
 {
  CopyBoard(NewMaze, Maze);
  tmp = SolveMazeREC(NewMaze, h, w-1, steps, &headOfNewList);
  if (tmp != -1)
   if (tmp < lowestSteps || lowestSteps == -1)
   {
    lowestSteps = tmp;
    headOfFinalList->next = headOfNewList;
   }
 }
 
 // Reset the START position
 Maze[startingPoint.Row][startingPoint.Column] = START;
 Maze[h][w] = PATH;
 
 // (If all directions are blocked, lowestSteps = -1)
 if (lowestSteps == -1)
 {
  return -1;
 }
 else
 {
  PaintAllPositionsInMazeThatAppearInFinalList(headOfFinalList, Maze);
  FreeList(headOfFinalList);  
  return steps + lowestSteps;
 }
}
 
int SolveMazeREC(int Maze[HEIGHT][WIDTH], int h, int w, int stepsUntilNow, node_t** outHeadOfList)
{
 int lowestSteps = -1;
 int NewMaze[HEIGHT][WIDTH];
 int tmp;
 struct Point startingPathPoint;
 struct node* headOfNewList;
 
 // If we've come here before in a faster way (Or another way in the same length), we can stop.
 if (MinStepsToEachPositionInMaze[h][w] <= stepsUntilNow)
 {
  (*outHeadOfList) = NULL; // (We don't really need this line)
  return -1;
 }
 else
 {
  MinStepsToEachPositionInMaze[h][w] = stepsUntilNow;
 }
 
 // -- If END
 if (Maze[h][w] == END)
 {
  (*outHeadOfList) = NULL;
  MinStepsToGoToEnd = stepsUntilNow;
  return 1;
 }
 
 // If we already crossed the "MinStepsToGoToEnd"
 if (MinStepsToGoToEnd <= stepsUntilNow)
 {
  (*outHeadOfList) = NULL; // (We don't really need this line)
  return -1;
 }
 
 startingPathPoint.Row = h;
 startingPathPoint.Column = w;
 (*outHeadOfList) = CreateNewList(startingPathPoint);
 Maze[h][w] = ARROW;
 
 // UP
 if (Maze[h-1][w] != WALL && Maze[h-1][w] != ARROW)
 {
  CopyBoard(NewMaze, Maze);
  tmp = SolveMazeREC(NewMaze, h-1, w, stepsUntilNow+1, &headOfNewList);
  if (tmp != -1)
   if (tmp < lowestSteps || lowestSteps == -1)
   {
    lowestSteps = tmp;
    (*outHeadOfList)->next = headOfNewList;
   }
 }
 
 // DOWN
 if (Maze[h+1][w] != WALL && Maze[h+1][w] != ARROW)
 {
  CopyBoard(NewMaze, Maze);
  tmp = SolveMazeREC(NewMaze, h+1, w, stepsUntilNow+1, &headOfNewList);
  if (tmp != -1)
   if (tmp < lowestSteps || lowestSteps == -1)
   {
    lowestSteps = tmp;
    (*outHeadOfList)->next = headOfNewList;
   }
 }
 
 // RIGHT
 if (Maze[h][w+1] != WALL && Maze[h][w+1] != ARROW)
 {
  CopyBoard(NewMaze, Maze);
  tmp = SolveMazeREC(NewMaze, h, w+1, stepsUntilNow+1, &headOfNewList);
  if (tmp != -1)
   if (tmp < lowestSteps || lowestSteps == -1)
   {
    lowestSteps = tmp;
    (*outHeadOfList)->next = headOfNewList;
   }
 }
 
 // LEFT
 if (Maze[h][w-1] != WALL && Maze[h][w-1] != ARROW)
 {
  CopyBoard(NewMaze, Maze);
  tmp = SolveMazeREC(NewMaze, h, w-1, stepsUntilNow+1, &headOfNewList);
  if (tmp != -1)
   if (tmp < lowestSteps || lowestSteps == -1)
   {
    lowestSteps = tmp;
    (*outHeadOfList)->next = headOfNewList;
   }
 }
 
 Maze[h][w] = PATH;
 
 // (If all directions are blocked, lowestSteps = -1)
 if (lowestSteps == -1)
 {
  (*outHeadOfList) = NULL; // (We don't really need this line)
  return -1;
 }
 else
 {
  return 1 + lowestSteps;
 }
}
 
 
struct Point FindStartingPoint(int Maze[HEIGHT][WIDTH])
{
 int startRow;
 int startColumn;
 struct Point StartingPoint;
 for (startRow = 0; startRow < HEIGHT; startRow++)
 {
  for (startColumn = 0; startColumn < WIDTH; startColumn++)
  {
   if (Maze[startRow][startColumn] == START)
   {
    StartingPoint.Column = startColumn;
    StartingPoint.Row = startRow;
    return StartingPoint;
   }
  }
 }
 
 printf("Error in FindStartingPoint\n");
 return StartingPoint;
}
 
struct Point FindStartingPathPoint(int Maze[HEIGHT][WIDTH])
{
 struct Point StartingPathPoint;
 StartingPathPoint = FindStartingPoint(Maze);
 
 if (Maze[StartingPathPoint.Row + 1][StartingPathPoint.Column] == PATH)
 {
  StartingPathPoint.Row += 1;
  return StartingPathPoint;
 } 
 else if (Maze[StartingPathPoint.Row - 1][StartingPathPoint.Column] == PATH)
 {
  StartingPathPoint.Row -= 1;
  return StartingPathPoint;
 }
 else if (Maze[StartingPathPoint.Row][StartingPathPoint.Column + 1] == PATH)
 {
  StartingPathPoint.Column += 1;
  return StartingPathPoint;
 }
 else if (Maze[StartingPathPoint.Row][StartingPathPoint.Column - 1] == PATH)
 {
  StartingPathPoint.Column -= 1;
  return StartingPathPoint;
 }
 else
 {
  printf("Error in FindStartingPathPoint\n");
  return StartingPathPoint;
 }
}
 
 
void InitMinStepsInMazeArray()
{
 int i, j;
 for (i = 0; i < HEIGHT; i++)
 {
  for (j = 0; j < WIDTH; j++)
  {
   MinStepsToEachPositionInMaze[i][j] = HEIGHT * WIDTH + 10; // Any number greater than number of positions in maze
  }
 }
}
 
void ShowBoard(int Board[HEIGHT][WIDTH])
{
 int row;
 int col;
 
 printf("Full maze:\n\n\n");
 for (row = 0; row < HEIGHT; row++)    // Loop through every row
 {
  for (col = 0; col < WIDTH; col++) // And every column
  {
   switch(Board[row][col])
   {
    case WALL  :
      putchar('\xDB');
      break;
 
    case PATH  :
      putchar(' ');
      break;
 
    case ARROW :
      putchar(ARROW);
      break;
    
    case START :
      putchar(START);
      break;
    
    case END   :
      putchar(END);
      break;
    
    default    :
      putchar('?');
      break;
   }
  }
  putchar('\n');
 }
 printf("\n\n\n");
}
 
void CopyBoard(int targetBoard[HEIGHT][WIDTH], int sourceBoard[HEIGHT][WIDTH])
{
 // Fast copy:
 memcpy(targetBoard, sourceBoard, WIDTH * HEIGHT * sizeof(int));
}
 
void InitializeTheMaze(int Board[HEIGHT][WIDTH])
{
 // Maze Option A:
 // #define HEIGHT   50
 // #define WIDTH    9
 int TmpBoard[HEIGHT][WIDTH] = {
  { WALL , WALL , START, WALL, WALL , WALL , WALL , WALL , WALL  },
  { WALL , PATH , PATH , PATH, PATH , PATH , PATH , PATH , WALL  },
  { WALL , PATH , WALL , WALL, WALL , PATH , WALL , WALL , WALL  },
  { WALL , PATH , WALL , PATH, WALL , PATH , PATH , PATH , WALL  },
  { WALL , WALL , WALL , PATH, WALL , PATH , WALL , PATH , WALL  },
  { WALL , PATH , WALL , PATH, PATH , PATH , PATH , PATH , WALL  },
  { WALL , PATH , WALL , WALL, WALL , WALL , WALL , PATH , WALL  },
  { WALL , PATH , PATH , PATH, PATH , PATH , PATH , PATH , WALL  },
  { WALL , PATH , WALL , WALL, WALL , WALL , WALL , WALL , WALL  },
  { WALL , PATH , PATH , PATH, PATH , PATH , PATH , PATH , WALL  },
  { WALL , WALL , WALL , WALL, WALL , WALL , WALL , PATH , WALL  },
  { WALL , PATH , PATH , PATH, PATH , PATH , PATH , PATH , WALL  },
  { WALL , PATH , WALL , WALL, PATH , WALL , WALL , PATH , WALL  },
  { WALL , PATH , PATH , PATH, PATH , PATH , PATH , PATH , WALL  },
  { WALL , PATH , WALL , PATH, WALL , PATH , WALL , PATH , WALL  },
  { WALL , PATH , WALL , PATH, PATH , PATH , WALL , PATH , WALL  },
  { WALL , PATH , WALL , WALL, WALL , WALL , WALL , PATH , WALL  },
  { WALL , PATH , PATH , PATH, PATH , PATH , PATH , PATH , WALL  },
  { WALL , WALL , WALL , WALL, WALL , WALL , WALL , PATH , WALL  },
  { WALL , PATH , PATH , PATH, PATH , PATH , WALL , PATH , WALL  },
  { WALL , WALL , PATH , WALL, WALL , WALL , WALL , PATH , WALL  },
  { WALL , PATH , PATH , PATH, WALL , PATH , PATH , PATH , WALL  },
  { WALL , PATH , WALL , WALL, WALL , PATH , WALL , WALL , WALL  },
  { WALL , PATH , PATH , PATH, WALL , PATH , PATH , PATH , WALL  },
  { WALL , PATH , WALL , PATH, WALL , PATH , WALL , PATH , WALL  },
  { WALL , PATH , WALL , PATH, PATH , PATH , PATH , PATH , WALL  },
  { WALL , WALL , WALL , WALL, WALL , PATH , WALL , PATH , WALL  },
  { WALL , PATH , PATH , PATH, PATH , PATH , PATH , PATH , WALL  },
  { WALL , PATH , WALL , PATH, PATH , WALL , PATH , WALL , WALL  },
  { WALL , PATH , PATH , PATH, WALL , WALL , PATH , WALL , WALL  },
  { WALL , WALL , WALL , PATH, WALL , WALL , PATH , WALL , WALL  },
  { WALL , PATH , PATH , PATH, PATH , WALL , PATH , PATH , WALL  },
  { WALL , WALL , WALL , PATH, WALL , WALL , PATH , PATH , WALL  },
  { WALL , PATH , PATH , PATH, WALL , WALL , WALL , PATH , WALL  },
  { WALL , PATH , WALL , PATH, WALL , PATH , WALL , PATH , WALL  },
  { WALL , PATH , WALL , PATH, PATH , PATH , PATH , PATH , WALL  },
  { WALL , PATH , PATH , PATH, PATH , WALL , PATH , PATH , WALL  },
  { WALL , PATH , WALL , PATH, PATH , PATH , PATH , PATH , WALL  },
  { WALL , WALL , WALL , WALL, PATH , WALL , PATH , WALL , WALL  },
  { WALL , PATH , PATH , PATH, PATH , WALL , PATH , PATH , WALL  },
  { WALL , PATH , WALL , WALL, WALL , WALL , PATH , WALL , WALL  },
  { WALL , PATH , PATH , PATH, WALL , PATH , PATH , PATH , WALL  },
  { WALL , PATH , WALL , WALL, WALL , WALL , PATH , WALL , WALL  },
  { WALL , PATH , PATH , PATH, WALL , PATH , PATH , PATH , WALL  },
  { WALL , PATH , WALL , PATH, WALL , PATH , WALL , PATH , WALL  },
  { WALL , PATH , WALL , PATH, PATH , PATH , PATH , PATH , WALL  },
  { WALL , WALL , WALL , WALL, WALL , WALL , WALL , PATH , WALL  },
  { WALL , PATH , PATH , PATH, PATH , PATH , PATH , PATH , WALL  },
  { WALL , PATH , PATH , WALL, WALL , WALL , PATH , PATH , WALL  },
  { WALL , END  , WALL , WALL, WALL , WALL , WALL , WALL , WALL  }
 };
 
 
 
 // Maze Option B:
 //// #define HEIGHT   9
 //// #define WIDTH    9
 //int TmpBoard[HEIGHT][WIDTH] = {
 // { WALL , WALL , START, WALL, WALL , WALL , WALL , WALL , WALL  },
 // { WALL , PATH , PATH , PATH, PATH , PATH , PATH , PATH , WALL  },
 // { WALL , PATH , WALL , WALL, WALL , PATH , WALL , WALL , WALL  },
 // { WALL , PATH , WALL , PATH, WALL , PATH , PATH , PATH , WALL  },
 // { WALL , WALL , WALL , PATH, WALL , PATH , WALL , PATH , WALL  },
 // { WALL , PATH , WALL , PATH, PATH , PATH , PATH , PATH , WALL  },
 // { WALL , PATH , WALL , WALL, WALL , WALL , WALL , PATH , WALL  },
 // { WALL , PATH , PATH , PATH, PATH , PATH , PATH , PATH , WALL  },
 // { WALL , END  , WALL , WALL, WALL , WALL , WALL , WALL , WALL  },
 //};
 
 CopyBoard(Board, TmpBoard);
}
 
void PaintAllPositionsInMazeThatAppearInFinalList(struct node* headOfFinalList, int Maze[HEIGHT][WIDTH])
{
 struct node* current = headOfFinalList;
 int i = 0;
    while (current != NULL) {
  Maze[current->point.Row][current->point.Column] = ARROW;
        current = current->next;
    }
}
 
 
 
// ** List Functions **
//
// - - Example of use: - -
//)
//struct node* head;
//struct node* endOfList;
//struct Point point1, point2, point3, point4;
//
//point1.Column = 3;
//point1.Row = 5;
//point2.Column = 30;
//// ... (init all points)
//
//endOfList = head = CreateNewList(point1);
//PushToList(&endOfList, point2);
//PushToList(&endOfList, point3);
//PushToList(&endOfList, point4);
// 
//PrintList(head);
//FreeList(head);
//
 
struct node* CreateNewList(struct Point point)
{
 struct node* headAndEndOfList;
 headAndEndOfList = (struct node*)malloc(sizeof(node_t));
 headAndEndOfList->point = point;
 headAndEndOfList->next = NULL;
 return headAndEndOfList;
}
 
void PrintList(struct node* head) {
    struct node* current = head;
    while (current != NULL) {
  printf("C: %d, R: %d\n", current->point.Column, current->point.Row);
        current = current->next;
    }
}
 
void FreeList(struct node* head) {
 struct node * p;
 while( head ) {
  p = head;
  head = head->next;
  free( p );
 }
}
 
// Adding an item to the beginning of the list
void PushToList(node_t ** refEnd, struct Point point) {
    node_t * new_node;
    new_node = (struct node*)malloc(sizeof(node_t));
 
 new_node->point = point;
 new_node->next = NULL;
 
 (*refEnd)->next = new_node;
 (*refEnd) = new_node;
}
 
int main()
{
 int Board [HEIGHT][WIDTH];
 int Steps;
 clock_t begin, end;
 double time_spent;
 
 InitializeTheMaze(Board);
 
 printf("* Start:\n\n");
 ShowBoard(Board);
 
 printf("* Program Answer:\n\n");
 begin = clock();
 Steps = SolveMaze(Board);
 end = clock();
 time_spent = (double)(end - begin) / CLOCKS_PER_SEC;
 
 if (Steps != -1) // Path found
 {
  printf("Number of steps: %d\n-----------------------\n", Steps);
  ShowBoard(Board);
 }
 else
 {
  printf("Maze cannot be solved! :(\n\n");
 }
 
 printf("Time:  %lf Seconds\n", time_spent);
 getchar();
}

הקוד הזה פותר את אותו המבוך ב-0.001 שניות (אפילו קצת פחות). מכובד ביותר.
ובנוסף: בהינתן מבוך עם כמה יציאות שונות, התוכנית תמצא את הדרך הקצרה ביותר ליציאה הקרובה ביותר.

אם נשדרג את הקוד בעתיד זה כנראה יהיה שדרוג בעניין הגרפיקה.

עד כאן להיום, נתראה בפעם הבאה.

.........
עריכה:
1. הנה השדרוג בעניין הגרפיקה: יצירה קלה של מבוכים חדשים עם ממשק משתמש גרפי
2. הגיבו לי שאלגוריתם דייקסטרה אמור לפתור בדיוק את אותה הבעיה. שווה לעיין. (תודה ל-CC_CC על המידע)
3. הקוד הנוכחי מקבל שגיאת StackOverflowException כשמזינים לו מבוכים גדולים במיוחד. צריך לבדוק איך ליעל את עניין הרקורסיה כך שתצרוך פחות משאבים מהמחסנית.

Barkai Class

דפים

יום רביעי, 20 ביוני 2018

מציאת הפתרון המהיר ביותר למבוך

2 תגובות: