#include <iostream>
#include <vector>
using namespace std;


const char WALL = '*';
const char WORKER = 'w';
const char WDEST = 'W';
const char BOX = 'b';
const char BDEST = 'B';
const char EMPTY = ' ';
const char DEST = '.';
typedef char Cell;
typedef vector<vector<Cell>> Puzzle;

struct Candidate
{
    Puzzle candidate;
    int parent_candidate;
};

struct Pos
{
    int col, row;
};

struct Step
{
    Pos from,to;
} ;


int size( vector<Cell>& data )
{
    return static_cast<int>(data.size());
}

int size( Puzzle& data )
{
    return static_cast<int>(data.size());
}

int size(vector<Candidate>& data)
{
    return static_cast<int>(data.size());
}


bool is_south_of_box(Puzzle& puzzle, Pos worker_pos)
{
     //Pre:
    assert(worker_pos.col > 0 && worker_pos.row > 0);
    //Post:
    //This function will be true if the worker is directly south of a box.

    int r = worker_pos.row;
    int c = worker_pos.col;
    if(puzzle[c-1][r] == BOX || puzzle[c-1][r] == BDEST )
    {
        return true;
    }
    return false;
}

bool is_north_of_box(Puzzle& puzzle, Pos worker_pos)
{
     //Pre:
    assert(worker_pos.col > 0 && worker_pos.row > 0);
    //Post:
    //This function will be true if the worker is directly north of a box.

    int r = worker_pos.row;
    int c = worker_pos.col;
    if(puzzle[c+1][r] == BOX || puzzle[c+1][r] == BDEST )
    {
        return true;
    }
    return false;
}

bool is_east_of_box(Puzzle& puzzle, Pos worker_pos)
{
     //Pre:
    assert(worker_pos.col > 0 && worker_pos.row > 0);
    //Post:
    //This function will be true if the worker is directly east of a box.


    int r = worker_pos.row;
    int c = worker_pos.col;
    if(puzzle[c][r-1] == BOX || puzzle[c][r-1] == BDEST )
    {
        return true;
    }
    return false;
}

bool is_west_of_box(Puzzle& puzzle, Pos worker_pos)
{
     //Pre:
    assert(worker_pos.col > 0 && worker_pos.row > 0);
    //Post:
    //This function will be true if the worker is directly west of a box.


    int r = worker_pos.row;
    int c = worker_pos.col;
    if(puzzle[c][r+1] == BOX || puzzle[c][r+1] == BDEST )
    {
        return true;
    }
    return false;
}


Pos find_worker(Puzzle& room)
{
    //Pre:
    assert(true);
    //Post:
    //This function will give the position of the worker

    for(int r = 0; r < size(room); r++)
        for(int c = 0; c < size(room[0]); c++)
            if(room[r][c] == 'w' || room[r][c] == 'W')
                return {r,c};
}

void move_box_west(Puzzle& puzzle)
{
     //Pre:
    assert(true);
    //Post:
    //After this function is called, the box directly west of the worker
    //will be one spot to the west. The spot where the box was will either
    //be an empty cell or a destination cell

    Pos wpos = find_worker(puzzle);


    if(puzzle[wpos.col][wpos.row - 2] == EMPTY)
        puzzle[wpos.col][wpos.row - 2] = BOX;
    else
        puzzle[wpos.col][wpos.row - 2] = BDEST;

    if(puzzle[wpos.col][wpos.row - 1] == BOX)
        puzzle[wpos.col][wpos.row - 1] = EMPTY;
    else
        puzzle[wpos.col][wpos.row - 1] = DEST;
}

void move_box_east(Puzzle& puzzle)
{
     //Pre:
    assert(true);
    //Post:
    //After this function is called, the box directly east of the worker
    //will be one spot to the east. The spot where the box was will either
    //be an empty cell or a destination cell

    Pos wpos = find_worker(puzzle);


    if(puzzle[wpos.col][wpos.row + 2] == EMPTY)
        puzzle[wpos.col][wpos.row + 2] = BOX;
    else
        puzzle[wpos.col][wpos.row + 2] = BDEST;

    if(puzzle[wpos.col][wpos.row + 1] == BOX)
        puzzle[wpos.col][wpos.row + 1] = EMPTY;
    else
        puzzle[wpos.col][wpos.row + 1] = DEST;
}

void move_box_south(Puzzle& puzzle)
{
    //Pre:
    assert(true);
    //Post:
    //After this function is called, the box directly south of the worker
    //will be one spot to the south. The spot where the box was will either
    //be an empty cell or a destination cell

    Pos wpos = find_worker(puzzle);

    if(puzzle[wpos.col + 2][wpos.row] == EMPTY)
        puzzle[wpos.col + 2][wpos.row] = BOX;
    else
        puzzle[wpos.col + 2][wpos.row] = BDEST;

    if(puzzle[wpos.col + 1][wpos.row] == BOX)
        puzzle[wpos.col + 1][wpos.row] = EMPTY;
    else
        puzzle[wpos.col + 1][wpos.row] = DEST;
}


void move_box_north(Puzzle& puzzle)
{
    //Pre:
    assert(true);
    //Post:
    //After this function is called, the box directly north of the worker
    //will be one spot to the north. The spot where the box was will either
    //be an empty cell or a destination cell


    Pos wpos = find_worker(puzzle);


    if(puzzle[wpos.col - 2][wpos.row] == EMPTY)
        puzzle[wpos.col - 2][wpos.row] = BOX;
    else
        puzzle[wpos.col - 2][wpos.row] = BDEST;

    if(puzzle[wpos.col - 1][wpos.row] == BOX)
        puzzle[wpos.col - 1][wpos.row] = EMPTY;
    else
        puzzle[wpos.col - 1][wpos.row] = DEST;
}


void move_worker_west(Puzzle& puzzle)
{
    //Pre:
    assert(true);
    //Post:
    //After this function is called, the worker will be moved one spot
    //to the west.  The spot where the worker was will either
    //be an empty cell or a destination cell

    Pos wpos = find_worker(puzzle);

    if(puzzle[wpos.col][wpos.row - 1] == EMPTY)
        puzzle[wpos.col][wpos.row - 1] = WORKER;
    else
        puzzle[wpos.col][wpos.row - 1] = WDEST;

    if(puzzle[wpos.col][wpos.row] == WORKER)
        puzzle[wpos.col][wpos.row] = EMPTY;
    else
        puzzle[wpos.col][wpos.row] = DEST;
}

void move_worker_east(Puzzle& puzzle)
{
    //Pre:
    assert(true);
    //Post:
    //After this function is called, the worker will be moved one spot
    //to the east.  The spot where the worker was will either
    //be an empty cell or a destination cell

    Pos wpos = find_worker(puzzle);

    if(puzzle[wpos.col][wpos.row + 1] == EMPTY)
        puzzle[wpos.col][wpos.row + 1] = WORKER;
    else
        puzzle[wpos.col][wpos.row + 1] = WDEST;

    if(puzzle[wpos.col][wpos.row] == WORKER)
        puzzle[wpos.col][wpos.row] = EMPTY;
    else
        puzzle[wpos.col][wpos.row] = DEST;
}

void move_worker_north(Puzzle& puzzle)
{
    //Pre:
    assert(true);
    //Post:
    //After this function is called, the worker will be moved one spot
    //to the north.  The spot where the worker was will either
    //be an empty cell or a destination cell

    Pos wpos = find_worker(puzzle);

    if(puzzle[wpos.col - 1][wpos.row] == EMPTY)
        puzzle[wpos.col - 1][wpos.row] = WORKER;
    else
        puzzle[wpos.col - 1][wpos.row] = WDEST;

    if(puzzle[wpos.col][wpos.row] == WORKER)
        puzzle[wpos.col][wpos.row] = EMPTY;
    else
        puzzle[wpos.col][wpos.row] = DEST;
}

void move_worker_south(Puzzle& puzzle)
{
    //Pre:
    assert(true);
    //Post:
    //After this function is called, the worker will be moved one spot
    //to the south.  The spot where the worker was will either
    //be an empty cell or a destination cell

    Pos wpos = find_worker(puzzle);

    if(puzzle[wpos.col + 1][wpos.row] == EMPTY)
        puzzle[wpos.col + 1][wpos.row] = WORKER;
    else
        puzzle[wpos.col + 1][wpos.row] = WDEST;

    if(puzzle[wpos.col][wpos.row] == WORKER)
        puzzle[wpos.col][wpos.row] = EMPTY;
    else
        puzzle[wpos.col][wpos.row] = DEST;
}

void go_north(Puzzle& puzzle)
{
    //Pre:
    assert(true);
    //Post:
    //After this function is called, the worker will be moved one spot
    //to the north, and if there is a box north of the worker, it will
    //be moved also. The spot where the worker was will either be an empty
    //spot or a destination.

    //find the worker
    Pos worker_pos = find_worker(puzzle);

    //check if the worker is south of a box
    if (is_south_of_box(puzzle, worker_pos))
        move_box_north(puzzle);

    move_worker_north(puzzle);
}

void go_south(Puzzle& puzzle)
{
    //Pre:
    assert(true);
    //Post:
    //After this function is called, the worker will be moved one spot
    //to the south, and if there is a box south of the worker, it will
    //be moved also. The spot where the worker was will either be an empty
    //spot or a destination.

    //find the worker
    Pos worker_pos = find_worker(puzzle);

    //check if the worker is south of a box
    if (is_north_of_box(puzzle, worker_pos))
        move_box_south(puzzle);

    move_worker_south(puzzle);
}

void go_east(Puzzle& puzzle)
{
    //Pre:
    assert(true);
    //Post:
    //After this function is called, the worker will be moved one spot
    //to the east, and if there is a box east of the worker, it will
    //be moved also. The spot where the worker was will either be an empty
    //spot or a destination.

    //find the worker
    Pos worker_pos = find_worker(puzzle);

    //check if the worker is south of a box
    if (is_west_of_box(puzzle, worker_pos))

        move_box_east(puzzle);


    move_worker_east(puzzle);
}

void go_west(Puzzle& puzzle)
{
    //Pre:
    assert(true);
    //Post:
    //After this function is called, the worker will be moved one spot
    //to the west, and if there is a box west of the worker, it will
    //be moved also. The spot where the worker was will either be an empty
    //spot or a destination.
    //find the worker
    Pos worker_pos = find_worker(puzzle);

    //check if the worker is south of a box
    if (is_east_of_box(puzzle, worker_pos))
        move_box_west(puzzle);

    move_worker_west(puzzle);
}

bool can_go_north(Puzzle& puzzle)
{
    //Pre:
    assert(true);
    //Post:
    //If the worker is able to go north (when there is no wall in the way,
    //with or without box) it will have returned true.
    Pos p = find_worker(puzzle);
    char tocell = puzzle[p.row][p.col];
    if(tocell == WALL)
        return false;
    if(tocell == EMPTY || tocell == DEST)
        return true;
    if((tocell == BOX  || tocell == BDEST) && (puzzle[p.row - 1][p.col] == EMPTY || puzzle[p.row - 1][p.col] == DEST))
        return true;
}


bool can_go_south(Puzzle& puzzle)
{
    //Pre:
    assert(true);
    //Post:
    //If the worker is able to go south (when there is no wall in the way,
    //with or without box) it will have returned true.

    Pos p = find_worker(puzzle);
    char tocell = puzzle[p.row][p.col];
    if(tocell == WALL)
        return false;
    if(tocell == EMPTY || tocell == DEST)
        return true;
    if((tocell == BOX || tocell == BDEST) && (puzzle[p.row + 1][p.col] == EMPTY|| puzzle[p.row + 1][p.col] == DEST))
        return true;
}


bool can_go_west(Puzzle& puzzle)
{
    //Pre:
    assert(true);
    //Post:
    //If the worker is able to go west (when there is no wall in the way,
    //with or without box) it will have returned true.

    Pos p = find_worker(puzzle);
    char tocell = puzzle[p.row][p.col];
    if(tocell == WALL)
        return false;
    if(tocell == EMPTY || tocell == DEST)
        return true;
    if((tocell == BOX || tocell == BDEST) && (puzzle[p.row][p.col - 1] == EMPTY || puzzle[p.row][p.col - 1] == DEST))
        return true;
}

bool can_go_east(Puzzle& puzzle)
{
    //Pre:
    assert(true);
    //Post:
    //If the worker is able to go east (when there is no wall in the way,
    //with or without box) it will have returned true.

    Pos p = find_worker(puzzle);
    char tocell = puzzle[p.row][p.col];
    if(tocell == WALL)
        return false;
    if(tocell == EMPTY || tocell == DEST)
        return true;
    if((tocell == BOX || tocell == BDEST) && (puzzle[p.row][p.col + 1] == EMPTY || puzzle[p.row][p.col + 1] == DEST))
        return true;
}


void print_puzzle(Puzzle& room)
{
    //Pre:
    assert(true);
    //Post:
    //This function will print the puzzle.
    for(int r = 0; r < size(room); r++)
    {
        for(int c = 0; c < size(room[0]); c++)
        {
            cout << room[r][c];
        }
        cout << endl;
    }
    cout << endl;
}


bool puzzle_present(vector<Candidate> c, int i, Puzzle newp)
{
    //Pre:
    assert(i > 0);
    //Post:
    //This function will return true if the new configuration has already
    //been considered

    while(i >= 0)
    {
        if(c[i].candidate == newp)
            return true;
        i = c[i].parent_candidate;
    }
    return false;
}

bool puzzle_ready(Puzzle p)
{
    //Pre:
    assert(true);
    //Post:
    //This function will return true if the puzzle is completed; ie if there
    //are no empty destination cells
    for(int r = 0; r < size(p); r++)
        for(int c = 0; c < size(p[0]); c++)
            if(p[r][c] == '.')
                return false;
    return true;
}

void show_path(vector<Candidate>& c, int i)
{
    //Pre:
    assert(true);
    //Post:
    //This function will recursively print the path we took to complete
    //the puzzle
    if(i < 0)
        print_puzzle(c[i].candidate);
    else
    {
        print_puzzle(c[i].candidate);
        show_path(c, c[i].parent_candidate);
    }
}

void solve_breadth_first(Puzzle& start)
{
    //Pre:
    assert(true);
    //post:
    //This function will use a breadth first search algorythm to find
    //a solution for the puzzle and if it exists it will print all the steps
    //needed to solve it.
    vector<Candidate> c = {{start, -1}};
    int i = 0;
    while(i < size(c) && !puzzle_ready(c[i].candidate))
    {
        Puzzle p = c[i].candidate;
        if(can_go_north(p))
        {
            //go north, and save to new puzzle
            Puzzle newp = p;
            go_north(newp);
            //check if new puzzle is really new
            if(!puzzle_present(c, i, newp))
            {
                Candidate newc = {newp, i};
                //save new puzzle to puzzle
                c.push_back(newc);
            }

        }
/*
        if(can_go_south(p))
        {
            Puzzle newp = p;
            go_south(newp);
            if(!puzzle_present(c, i, newp))
                Candidate newc = {newp, i};
                c.push_back(newc);

        }

        if(can_go_west(p))
        {
            Puzzle newp = p;
            go_west(newp);
            if(!puzzle_present(c, i, newp))
                Candidate newc = {newp, i};
                c.push_back(newc);
        }

        if(can_go_east(p))
        {
            Puzzle newp = p;
            go_south(newp);
            if(!puzzle_present(c, i, newp))
                Candidate newc = {newp, i};
                c.push_back(newc);
        }
*/
        i++;
    }
    if(i<size(c)) show_path(c, i);
}


int main()
{
    Puzzle room =               {   {'*','*','*','*','*','*','*','*',' ','*'} ,
                                    {'*',' ',' ',' ',' ',' ',' ','b','B','*'} ,
                                    {'*','B',' ',' ',' ',' ',' ','B','W','*'} ,
                                    {'*',' ',' ','*','*','*','*','.',' ','*'} ,
                                    {'*','*','*','*','*','*','*','*',' ','*'} };
    print_puzzle(room);
    go_north(room);
    print_puzzle(room);
    go_west(room);
    print_puzzle(room);
    go_south(room);
    print_puzzle(room);
    go_east(room);
    print_puzzle(room);





    return 0;



}