מציאת הדרך הקצרה ביותר במבוך – ברוט פורס רקורסיבי

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

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

לכתוב תוכנית שתמצא דרך כלשהי במבוך היא קלה מאד ולכן, בגלל הקאטץ' שיש כאן, התרגיל עניין אותי וכתבתי לו פתרון, כמובן, רקורסיבי, אך יש לשים לב שהאלגוריתם הוא ברוט פורס שעובר על כל הדרכים האפשריות ולכן אלגוריתם זה לא אפקטיבי במיוחד כיוון ובמקרים אמיתיים יהיה איטי מאד ויבדוק דרכים רבות – בשביל לכתוב פתרון שלא ירוץ על כל הדרכים דרוש אלגוריתם חכם יותר!

הפונקציה SolveMaze מקבלת מערך דו-מימדי של מספרים כאשר 0 מייצג דרך שניתן ללכת בה ו-1- מייצג קיר, פרמטרים CurrentRow/CurrentCol שמציינים נקודת התחלה ופרמטרים EndingRow/EndingCol שמציינים את היעד – סוף המבוך. הפונקציה תחזיר את Steps – מספר הצעדים ותציב במערך הדו-מימדי מספרים מ-1 עד Steps שמייצגים את המשבצות לפי סדר התקדמות – בצורה מינימלית.

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

פלט בתחתית הקוד.

/************************************************
*************************************************
*************************************************
Shortest Path Finding Algorithm, 20th June, 2010.
By Symbol © 2010.
*************************************************
*************************************************
************************************************/

#include <stdio.h>
#include <memory.h>

#define HEIGHT    50
#define WIDTH    9

#define WALL    -1
#define PATH    0

#define UP        24
#define DOWN    25
#define RIGHT    26
#define LEFT    27

int SolveMaze(int Maze[HEIGHT][WIDTH],
 int CurrentRow, int CurrentCol,
 int EndingRow, int EndingCol)
{
 static int Steps = 1;
 static int Path[HEIGHT][WIDTH];

 if (CurrentRow < 0 || CurrentRow >= HEIGHT ||
 CurrentCol < 0 || CurrentCol >= WIDTH) //Out of maze range - return.
 return -1;

 if (Maze[CurrentRow][CurrentCol] == PATH) //If the square is free, not a wall and we haven't been there yet
 {
 Maze[CurrentRow][CurrentCol] = Steps; //Set the square to be step number: Steps.

 if (CurrentRow == EndingRow && CurrentCol == EndingCol) //If we've reached our destination
 {
 if (Path[EndingRow][EndingCol] == PATH || Path[EndingRow][EndingCol] > Steps) //And if this path is shorter than the previous (basically, path length is held at our destination cell)
 memcpy(Path, Maze, WIDTH * HEIGHT * sizeof(int)); //Copy the maze
 }
 else //if we're not at our destination
 {
 Steps++; //Increase steps by 1.
 for (int row = -1; row <= 1; row++) //Vertical direction - up, down or none.
 {
 for (int col = -1; col <= 1; col++) //Horizontal direction - left, right or none.
 {
 if ((row != 0) ^ (col != 0)) //If and only if row isn't 0 OR col isn't 0, however not both or none, so one must be true!
 SolveMaze(Maze, CurrentRow + row, CurrentCol + col, EndingRow, EndingCol); //Check the next square for correct/shortest path. ignoring return value, result will be held at the static array.
 }
 }
 Steps--; //Decrease steps by 1.
 }

 Maze[CurrentRow][CurrentCol] = PATH; //Restore the current square's value from "step number: Steps" to PATH (0) to return and check the next path without the current path intersecting and interfering with the next path check.
 }

 if (Steps == 1) //If the Steps is 1, aka steps = 1, meaning we're returning back to user.
 { //This check is used to prevent extra memory copying - can save a lot of comuting time and power.
 memcpy(Maze, Path, WIDTH * HEIGHT * sizeof(int)); //Copy the shortest path from static array, Path.
 memset(Path, 0, WIDTH * HEIGHT * sizeof(int)); //Fill the static array Path with zeros for future use.
 return Maze[EndingRow][EndingCol] - 1; //Starting point (0 steps) contains 1, thus return Ending Point's value - 1.
 }

 return -1; //Still not returning to user or path finding failed, return -1 indicating failure. (ignored within current function)
}

int main()
{
 int Board[HEIGHT][WIDTH] = { //Initialize the maze
 { WALL, WALL, WALL, 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, WALL, WALL, WALL, WALL, WALL, WALL, WALL, WALL }
 };

 //Pass Board as the maze, { 1, 1 } as the starting point and { 48, 1 } as the ending point.
 int Steps = SolveMaze(Board, 1, 1, 48, 1);
 if (Steps != -1) //Path found
 {
 printf("%d steps\n-----------------------\n", Steps);

 for (int row = 0; row < HEIGHT; row++) //Loop through every row
 {
 for (int col = 0; col < WIDTH; col++) //And every column
 {
 if (Board[row][col] == 1) //If it is the starting point
 {
 putchar('\x01'); //Then draw a smily
 }
 else if (Board[row][col] != WALL && Board[row][col] != PATH) //Not a wall/empty path
 {
 if (Board[row][col] <= Steps) //Still not last step
 {
 for (int r = -1; r <= 1; r++) //Search for the next path
 {
 for (int c = -1; c <= 1; c++) //To get the correct direction
 {
 if ((r != 0) ^ (c != 0)) //If and only if direction is one of up, down, left or right.
 {
 if (Board[row + r][col + c] == Board[row][col] + 1) //The square in that direction is our next step
 {
 char arrow; //ASCII representation of the arrow of our direction
 if (r == 0)
 arrow = (c == 1 ? RIGHT : LEFT);
 else
 arrow = (r == 1 ? DOWN : UP);

 putchar(arrow);
 c = r = 2; //break 2 loops
 }
 }
 }
 }
 }
 else //if (Board[row][col] == Steps + 1), aka last step
 {
 printf("X"); //Our destination!!!
 }
 }
 else //if (Board[row][col] <= PATH)
 {
 putchar(Board[row][col] == WALL ? '\xDB' : ' '); //Draw either a wall or an empty path
 }
 } //for (columns)

 putchar('\n');
 } //for (rows)
 } //if (Steps == 0)
 else
 {
 printf("Maze cannot be solved! :(\n");
 }

 return 0;
}

//FIN!

/*
77 steps
-----------------------
█████████
█☺→→→↓  █
█ ███↓███
█ █ █→→↓█
███ █ █↓█
█ █    ↓█
█ █████↓█
█↓←←←←←←█
█↓███████
█→→→→→→↓█
███████↓█
█      ↓█
█ ██ ██↓█
█      ↓█
█ █ █ █↓█
█ █   █↓█
█ █████↓█
█      ↓█
███████↓█
█     █↓█
██ ████↓█
█   █↓←←█
█ ███↓███
█   █↓  █
█ █ █↓█ █
█ █  ↓  █
█████↓█ █
█    →↓ █
█ █  █↓██
█   ██↓██
███ ██↓██
█    █→↓█
███ ██ ↓█
█   ███↓█
█ █ █ █↓█
█ █   ↓←█
█    █↓ █
█ █   ↓ █
████ █↓██
█    █↓ █
█ ████↓██
█   █ ↓ █
█ ████↓██
█   █ →↓█
█ █ █ █↓█
█ █    ↓█
███████↓█
█↓←←←←←←█
█X ███  █
█████████
*/