Solve_The_Maze_V-Symbol

// The code of Symbol/Skyance (with few changes)
// 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/

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

#include <stdio.h>
#include <memory.h>
#include <time.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];

    int row;
    int col;

    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 (row = -1; row <= 1; row++) //Vertical direction - up, down or none.
            {
                for (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;
    int row;
    int col;
    int r;
    int c;
    char arrow; //ASCII representation of the arrow of our direction
    clock_t begin, end;
    double time_spent;

    begin = clock();
    Steps = SolveMaze(Board, 1, 1, 48, 1);
    end = clock();
    time_spent = (double)(end - begin) / CLOCKS_PER_SEC;

    if (Steps != -1) //Path found
    {
        printf("%d steps\n-----------------------\n", Steps);

        for (row = 0; row < HEIGHT; row++) //Loop through every row
        {
            for (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 (r = -1; r <= 1; r++) //Search for the next path
                        {
                            for (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
                                    {
                                        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");
    }

    printf("Time:  %lf Seconds\n", time_spent);
    getchar();

}