#include <iostream>
#include <fstream>
#include "function.h"

using namespace std;

void Crossing::solve()
{
    _npeople.push_back(0);
    _npeople.push_back(0);
    _npeople.push_back(1);
    list<State> a;
    a.push_back(_npeople);
    _paths.insert(a);
    while(!_paths.empty())
    {
        set<list<State>> newPaths;
        set<list<State>> oldPaths;

        for (auto p : _paths)//p is a list<State>
        {
            //cout << "!!!!";
            _explored.insert(p.back());//last elem. of p
            //cout << "!!!!";
            auto nextStates = extend(p.back());
            //cout << nextStates.size() << endl;
            for (auto s : nextStates)
            {
                if (found(s))
                {
                    //cout << "!!!!";
                    auto np = p;
                    np.push_back(s);
                    _solutions.insert(np);
                }
                else
                {
                    auto search = _explored.find(s);
                    if (search == _explored.cend())
                    {
                        auto np = p;
                        np.push_back(s);
                        newPaths.insert(np);
                    }
                }
            }
            oldPaths.insert(p);
        }

        for (auto p : oldPaths)
        {
            _paths.erase(p);
        }
        for (auto p : newPaths)
        {
            _paths.insert(p);
            //cout << "!!!!\n";
        }
      /*  if(!_paths.empty())
            cout << 1234;*/
        //--steps;
    }
}
set<State> Crossing::extend(State s)
{
    set<State> ss;
    int shipmem[5][2] = {{1,0},{0,1},{1,1},{2,0},{0,2}};
    for (int i = 0; i <= 4; i++)
    {
        //
        State newstate;
        if (s[4] == 1)
        {
            newstate.push_back(s[0]-shipmem[i][0]);
            newstate.push_back(s[1]-shipmem[i][1]);
            newstate.push_back(s[2]+shipmem[i][0]);
            newstate.push_back(s[3]+shipmem[i][1]);
            newstate.push_back(-1);
            //cout << newstate[0] << newstate[1] << newstate[2] << newstate[3] << endl;
        }
        else
        {
            newstate.push_back(s[0]+shipmem[i][0]);
            newstate.push_back(s[1]+shipmem[i][1]);
            newstate.push_back(s[2]-shipmem[i][0]);
            newstate.push_back(s[3]-shipmem[i][1]);
            newstate.push_back(1);
        }

        if (valid(newstate))
        {
            ss.insert(newstate);
            //cout << "?";
        }
    }
    return ss;
}
bool Crossing::valid(State s)
{
    if (s[1] > s[0] && s[0] != 0)
        return false;
    if (s[3] > s[2] && s[2] != 0)
        return false;
    if (s[0] < 0 || s[1] < 0 || s[2] < 0 || s[3] < 0)
        return false;
    return true;
}
bool Crossing::found(State s)
{
    if (s[0] == 0 && s[1] == 0)
    {
        return true;
    }
    return false;
}
State Crossing::Go(State s, int missionary, int cannibal)
{

}