taolao.cpp

#include <iostream>
#include <queue>
#include <stack>
#include <algorithm>
#include <malloc.h>

using namespace std;

#define MAX_GHOST 3
#define MAX_PEOPLE 3
#define POSITION_A 1
#define POSITION_B 0


typedef struct{
    int people;
    int ghost;
    int boat_location;
}State;

typedef struct Node{
    State state;
    struct Node* Parent;
    int no_function;
}Node;

void makeNullState(State *state)
{
    state->ghost = 0;
    state->people = 0;
    state->boat_location = 0;
}
int isWin(State state)
{
    return ( (state.people == MAX_PEOPLE) && (state.ghost == MAX_GHOST ) && (state.boat_location == POSITION_A) );
}

int onePeopleToA(State cur_state, State *result)
{
    if(cur_state.people < 3)
    {
        result->people = cur_state.people + 1;
        result->ghost = cur_state.ghost;
        result->boat_location = POSITION_A;
        return 1;
    }
    return 0;
}
int oneGhostToA(State cur_state, State *result)
{
    if(cur_state.ghost < 3)
    {
        result->ghost = cur_state.ghost + 1;
        result->people = cur_state.people;
        result->boat_location = POSITION_A;
        return 1;
    }
    return 0;
}
int twoPeopleToA(State cur_state, State *result)
{
    if(cur_state.people < 2)
    {
        result->people = cur_state.people + 2;
        result->ghost = cur_state.ghost;
        result->boat_location = POSITION_A;
        return 1;
    }
    return 0;
}
int twoGhostToA(State cur_state, State *result)
{
    if(cur_state.ghost < 2)
    {
        result->ghost = cur_state.people + 2;
        result->people = cur_state.people;
        result->boat_location = POSITION_A;
        return 1;
    }
    return 0;
}
int onePeopleOneGhostA(State cur_state, State *result)
{
    if(cur_state.people < 3 && cur_state.ghost < 3)
    {
        result->people = cur_state.people + 1;
        result->ghost  = cur_state.ghost + 1;
        result->boat_location = POSITION_A;
        return 1;
    }

    return 0;
}

int onePeopleToB(State cur_state, State *result)
{
    if(cur_state.people > 0)
    {
        result->people = cur_state.people - 1;
        result->ghost = cur_state.ghost;
        result->boat_location = POSITION_B;
        return 1;
    }
    return 0;
}
int oneGhostToB(State cur_state, State *result)
{
    if(cur_state.ghost > 0)
    {
        result->ghost  = cur_state.ghost - 1;
        result->people = cur_state.people;
        result->boat_location = POSITION_B;
        return 1;
    }
    return 0;
}
int twoPeopleToB(State cur_state, State *result)
{
    if(cur_state.people > 1)
    {
        result->people = cur_state.people - 2;
        result->ghost = cur_state.ghost;
        result->boat_location = POSITION_B;
        return 1;
    }
    return 0;
}
int twoGhostToB(State cur_state, State *result)
{
    if(cur_state.ghost > 1)
    {
        result->ghost = cur_state.ghost - 2;
        result->people = cur_state.people;
        result->boat_location = POSITION_B;
        return 1;
    }
    return 0;
}
int onePeopleOneGhostB(State cur_state, State *result)
{
    if(cur_state.people > 0 && cur_state.ghost > 0)
    {
        result->people = cur_state.people - 1;
        result->ghost  = cur_state.ghost - 1;
        result->boat_location = POSITION_B;
        return 1;
    }
    return 0;
}

int call_operation(State cur_state, State * result, int opt)
{
    switch (opt) {
        case 1: return onePeopleToA(cur_state, result);
        case 2: return oneGhostToA(cur_state, result);
        case 3: return twoPeopleToA(cur_state, result);
        case 4: return twoGhostToA(cur_state, result);
        case 5: return onePeopleOneGhostA(cur_state, result);
        case 6: return onePeopleToB(cur_state, result);
        case 7: return oneGhostToB(cur_state, result);
        case 8: return twoPeopleToB(cur_state, result);
        case 9: return twoGhostToB(cur_state, result);
        case 10: return onePeopleOneGhostB(cur_state, result);
        default: cout << "ERROR";  return 0;
    }
}
void print_State(State state, int option)
{
    if((option >= 1) && (option <= 5))
    {
        cout << endl << option << " | A: P"<< state.people << "-G" << state.ghost << " <- B: P" << 3-state.people << "-G" << 3-state.ghost << endl;
    }else
    {
        cout << endl << option << " | A: P"<< state.people << "-G" << state.ghost << " -> B: P" << 3-state.people << "-G" << 3-state.ghost << endl;
    }
}
int isDangersInA(State state)
{


    if( state.boat_location == POSITION_A )
    {
        if(state.ghost > state.people)
        {
            return 1;
        }
    }

    return 0;
}
int isDangersInB(State state)
{


    if( state.boat_location == POSITION_B )
    {
        if(3 - state.ghost >  3 - state.people)
        {
            return 1;
        }
    }

    return 0;
}
Node* DFS(State state)
{
    Node *root = (Node*)malloc(sizeof(Node));
    root->state = state;
    root->Parent = NULL;
    root->no_function = 0;
    queue<Node*> sOpen;
    queue<Node*> sClose;
    sOpen.push(root);
    int test = 1;

    while(!sOpen.empty())
    {
        Node *node = sOpen.front();
        sOpen.pop();
        sClose.push(node);
        if(isWin(node->state))
        {
            return node;
        }
        cout <<   endl << test <<"------------\n";
        test++;
        for(int i = 1; i <= 10; i++)
        {
            State newState;
            makeNullState(&newState);
            if(call_operation(node->state, &newState, i))
            {
//
                if(isDangersInA(newState) || isDangersInB(newState))
                    continue;

//                print_State(newState,i);

                Node * newNode = (Node*)malloc(sizeof(Node));
                newNode->state = newState;
                newNode->Parent = node;
                newNode->no_function = i;
                sOpen.push(newNode);
            }

        }

    }
    return NULL;
}
void print_WaysToGetGoal(Node *node)
{
    stack<Node*> stackPrint;

    while(node->Parent != NULL)
    {
        stackPrint.push(node);
        node = node->Parent;
    }
    stackPrint.push(node);
    int action = 0;
    while(!stackPrint.empty())
    {
        print_State(stackPrint.top()->state,action);
        action++;
        stackPrint.pop();
    }
}
int main()
{
    State currentState = {0, 0, POSITION_B};
    Node * result = DFS(currentState);
    print_WaysToGetGoal(result);
    return 0;
}