#include <iostream>
#include <conio.h>
#include <iomanip>
#include <vector>
#define FALSE 0
#define TRUE 1

using namespace std;
static int steps;
int n,colsend,rowend,column,row,blockrow,blockcol,;

// Symbols:
// '.' = open
// '#' = blocked
// 'R' = robot
// 'X' = goal
// '+' = path

void displaymaze(vector<vector<char> >);
void display(vector<vector<char> >);
int find_path(int x, int y,vector<vector<char> >);


int main()
{
    int choice,numsquare,numblock;
    int limit = 1;
    int nonvisit = 0;

    cout <<"Set the value of n x n squares area:"<<endl;
    cout <<"Enter the value for n:";
    cin >> n;
    vector<vector<char> > square(n,vector<char>(n,'.'));

    display(square);
    cout<<"\nThis is the square area robot could move."<<endl;
    cout <<"\nNow specific the robot starting point and destination to move:"<<endl;

    cout <<"Enter which row to start(starting from 0) :";
    do
    {
        cin >> row;
        if (row > (n-1) || row<0)
            cout<<"The row size is not in range,please enter again:";
    }
    while (row > (n-1) || row<0);
    cout <<"Enter which column to start(starting from 0) :";
    do
    {
        cin >> column;
        if (column > (n-1) || column <0)
            cout<<"The column size is not in range,please enter again:";
    }
    while (column > (n-1) || column <0);

    cout <<"Enter which row to end(starting from 0) :";
    do
    {
        cin >> rowend;
        if (rowend > (n-1)||rowend <0)
            cout<<"The column size is not in range,please enter again:";
    }
    while (rowend >(n-1)||rowend <0);
    cout <<"Enter which column to end(starting from 0) :";
    do
    {
        cin >> colsend;
        if (colsend > (n-1)||colsend <0)
            cout<<"The column size is not in range,please enter again:";
    }
    while (colsend > (n-1)||colsend <0);
    system("cls");


    cout<<"The row and column of the starting point is ("<<row<<","<<column<<")"<<endl;
    cout<<"The row and column of the destination is ("<<rowend<<","<<colsend<<")"<<endl;
    square[row][column]='R';
    square[rowend][colsend]='X';
    display(square);
    cout <<"Run the maze area with or without block:"<<endl;
    cout <<"1.Without block"<<endl;
    cout <<"2.With block"<<endl;
    cout <<"Enter your selection <1><2>";
    cin >> choice;

    if (choice ==1)
    {
        system("cls");

        if ( find_path(column, row,square) == TRUE )
        {
            cout<<"Success!\n";
        }
        else
            cout<<"Failed\n";

        cout<<"Total Steps = "<<steps;

    }

    if (choice ==2)
    {
        system("cls");
        cout <<"How many block to be insert:"<<endl;
        cout <<"1.One"<<endl;
        cout <<"2.More than one"<<endl;
        cout <<"Enter your selection <1>/2>";
        cin >>numsquare;
        if (numsquare==1)
        {
            cout <<"Which position to insert the block:"<<endl;
            cout <<"Block row:";
            cin >> blockrow;
            cout <<"Block column:";
            cin >> blockcol;
            square[blockrow][blockcol]='#';
            if ( find_path(column, row,square) == TRUE )
            {
                cout<<"Success!\n";
            }
            else
                cout<<"Failed\n";

            cout<<"Total Steps = "<<steps;
        }
        if (numsquare==2)
        {
            cout <<"How many block to be insert:"<<endl;
            cin >> numblock;
            while (limit<=numblock)
            {
                cout <<"Which position to insert the block "<<limit<<":"<<endl;
                cout <<"Block row:";
                cin >> blockrow;
                cout <<"Block column:";
                cin >> blockcol;
                square[blockrow][blockcol]='#';
                limit++;
            }

            if ( find_path(column, row,square) == TRUE )
            {
                cout<<"\nSuccess!\n";
            }
            else
                cout<<"Failed\n";

            cout<<"Total Steps = "<<steps<<endl;
        }


    }



    getch();
    return 0;
}
// main()


void displaymaze(vector<vector<char> >maze)
{
    cout<<"MAZE:\n";

    for (int a=0;a<n;a++)
    {
        cout<<setw(7);
        for (int b=0;b<n;b++)
        {
            cout<<maze[a][b];
            cout<<setw(3);
        }
        cout<<endl;
    }

    return;
}

void display(vector<vector<char> >square)
{
    for (int x=0;x<n;x++)
    {
        cout<<setw(7);
        for (int y=0;y<n;y++)
        {
            cout << square[x][y];
            cout<<setw(3);
        }
        cout<<endl;
    }
}


int
find_path(int x, int y,vector<vector<char> >square)
{
    int nonvisit = 0;
    // If x,y is outside maze, return false.
    if ( x < 0 || x > n - 1 || y < 0 || y > n - 1 ) return FALSE;
// If x,y is the goal, return true.


    if ( square[y][x] == 'X')
    {
        displaymaze(square);
        for (int e=0;e<n;e++)
        {
            for (int f=0;f<n;f++)
            {
                if (square[e][f]=='.')
                {
                    nonvisit+=1;
                }

            }
        }
        cout<<"Total non visited steps = "<<nonvisit<<endl;
        return TRUE;
    }



// If x,y is not open, return false.
    if ( square[y][x] != '.' && square[y][x] != 'R' ) return FALSE;


    // Mark x,y part of solution path.
    if ( square[y][x] == '.' )square[y][x] = '+';
    steps++;


    // If find_path North of x,y is true, return true.
    if ( find_path(x, y - 1,square) == TRUE ) return TRUE;

    // If find_path East of x,y is true, return true.
    if ( find_path(x + 1, y,square) == TRUE ) return TRUE;

    // If find_path South of x,y is true, return true.
    if ( find_path(x, y + 1,square) == TRUE ) return TRUE;

    // If find_path West of x,y is true, return true.
    if ( find_path(x - 1, y,square) == TRUE ) return TRUE;

    //mark the repeat steps
    square[y][x]='X';
    return FALSE;
}