#include <iostream>
#include <vector>
#include <array>
#include <queue>
#include <algorithm>


using namespace std;

vector<array<int, 7>> expandir(array<int, 7> no){
    vector<array<int, 7>> sucessores;
    array<int, 7> aux;
    aux = no;

    if (aux[0] == 0 && aux[1] == 0 && aux[2] == 0 && aux[3] == 0 && aux[4] == 3 && aux[5] == 3 && aux[6] == -1){ //Se 4 n�o tiver cheio, pode encher
        aux = {0,0,1,1,2,2,0};
        sucessores.push_back(aux);
        return sucessores;
    }

    if (aux[0] == 0 && aux[1] == 1 && aux[2] == 1 && aux[3] == 0 && aux[4] == 2 && aux[5] == 2 && aux[6] == 1){ //Se 4 n�o tiver cheio, pode encher
        aux = {0,1,0,2,3,0,0};
        sucessores.push_back(aux);
        return sucessores;
    }

    if (aux[0] == 0 && aux[1] == 2 && aux[2] == 0 && aux[3] == 1 && aux[4] == 3 && aux[5] == 0 && aux[6] == 1){ //Se 4 n�o tiver cheio, pode encher
        aux = {0,2,2,0,1,1,0};
        sucessores.push_back(aux);
        return sucessores;
    }

    if (aux[0] == 1 && aux[1] == 1 && aux[2] == 1 && aux[3] == 1 && aux[4] == 1 && aux[5] == 1 && aux[6] == 1){ //Se 4 n�o tiver cheio, pode encher
        aux = {1,1,2,0,0,2,0};
        sucessores.push_back(aux);
        return sucessores;
    }

    if (aux[0] == 3 && aux[1] == 0 && aux[2] == 0 && aux[3] == 1 && aux[4] == 0 && aux[5] == 2 && aux[6] == 1){ //Se 4 n�o tiver cheio, pode encher
        aux = {3,0,0,2,0,1,0};
        sucessores.push_back(aux);
        return sucessores;
    }

    if (aux[0] == 3 && aux[1] == 1 && aux[2] == 0 && aux[3] == 1 && aux[4] == 0 && aux[5] == 1 && aux[6] == 1){ //Se 4 n�o tiver cheio, pode encher
        aux = {3,1,0,2,0,0,0};
        sucessores.push_back(aux);
        return sucessores;
    }

    if (aux[0] == 0 && aux[1] == 0 && aux[2] == 1 && aux[3] == 1 && aux[4] == 2 && aux[5] == 2 && aux[6] == 0){ //Se 4 n�o tiver cheio, pode encher
        aux = {0,1,1,0,2,2,1};
        sucessores.push_back(aux);
        return sucessores;
    }

    if (aux[0] == 0 && aux[1] == 1 && aux[2] == 0 && aux[3] == 2 && aux[4] == 3 && aux[5] == 0 && aux[6] == 0){ //Se 4 n�o tiver cheio, pode encher
        aux = {0,2,0,1,3,0,1};
        sucessores.push_back(aux);
        return sucessores;
    }

    if (aux[0] == 0 && aux[1] == 2 && aux[2] == 2 && aux[3] == 0 && aux[4] == 1 && aux[5] == 1 && aux[6] == 0){ //Se 4 n�o tiver cheio, pode encher
        aux = {1,1,1,1,1,1,1};
        sucessores.push_back(aux);
        return sucessores;
    }

    if (aux[0] == 1 && aux[1] == 1 && aux[2] == 2 && aux[3] == 0 && aux[4] == 0 && aux[5] == 2 && aux[6] == 0){ //Se 4 n�o tiver cheio, pode encher
        aux = {3,0,0,1,0,2,1};
        sucessores.push_back(aux);
        return sucessores;
    }

    if (aux[0] == 3 && aux[1] == 0 && aux[2] == 0 && aux[3] == 2 && aux[4] == 0 && aux[5] == 1 && aux[6] == 0){ //Se 4 n�o tiver cheio, pode encher
        aux = {3,1,0,1,0,1,1};
        sucessores.push_back(aux);
        return sucessores;
    }

    if (aux[0] == 3 && aux[1] == 1 && aux[2] == 0 && aux[3] == 2 && aux[4] == 0 && aux[5] == 0 && aux[6] == 0){ //Se 4 n�o tiver cheio, pode encher
        aux = {3,3,0,0,0,0,-1};
        sucessores.push_back(aux);
        return sucessores;
    }

    return sucessores;
}

bool testarObjetivo(vector<array<int, 7>> solucao){

    for(vector<array<int, 7>>::size_type i = 0; i != solucao.size(); i++){
        if(solucao[i][0] == 3 && solucao[i][1] == 3 && solucao[i][2] == 0 && solucao[i][3] == 0 && solucao[i][4] == 0 && solucao[i][5] == 0){
            return true;
        }
    }
    return false;
}

vector<array<int, 7>> buscaEmArvore(array<int, 7> estadoInicial){
    queue<array<int, 7>> borda;
    vector<array<int, 7>> solucao,resposta;
    array<int, 7> no;

    borda.push(estadoInicial);
    resposta.push_back(estadoInicial);

    while (!borda.empty()){
        no = borda.front();
        borda.pop();
        solucao = expandir(no);
        resposta.insert(resposta.end(), solucao.begin(), solucao.end());
        if(testarObjetivo(solucao)){
            return resposta;
        }

        for(vector<array<int, 7>>::size_type i = 0; i != solucao.size(); i++){
            borda.push(solucao[i]);
        }
    }
    solucao.clear();
    return resposta;
}

struct target_less
{
    template<class It>
    bool operator()(It const &a, It const &b) const { return *a < *b; }
};
struct target_equal
{
    template<class It>
    bool operator()(It const &a, It const &b) const { return *a == *b; }
};
template<class It> It uniquify(It begin, It const end)
{
    std::vector<It> v;
    v.reserve(static_cast<size_t>(std::distance(begin, end)));
    for (It i = begin; i != end; ++i)
    { v.push_back(i); }
    std::sort(v.begin(), v.end(), target_less());
    v.erase(std::unique(v.begin(), v.end(), target_equal()), v.end());
    std::sort(v.begin(), v.end());
    size_t j = 0;
    for (It i = begin; i != end && j != v.size(); ++i)
    {
        if (i == v[j])
        {
            using std::iter_swap; iter_swap(i, begin);
            ++j;
            ++begin;
        }
    }
    return begin;
}

int main()
{
    array<int, 7> problema = {0,0,0,0,3,3,-1};
    vector<array<int, 7>> resposta = buscaEmArvore(problema);
    resposta.erase(uniquify(resposta.begin(), resposta.end()), resposta.end());
    for(vector<array<int, 7>>::size_type i = 0; i != resposta.size(); i++){
        switch(resposta[i][6])
        {
        case -1:
            cout<<"Estao "<<resposta[i][0]<<" missionarios e "<<resposta[i][1]<<" canibais na margem esquerda e "<<resposta[i][4]<<" missionarios e "<<resposta[i][5]<<" canibais na margem direita."<<endl;
            break;
        case 0:
            cout<<"MARGEM ESQUERDA: "<<resposta[i][0]<<" missionarios e "<<resposta[i][1]<<" canibais      ||        "<<"<------ BARCO: "<<resposta[i][2]<<" missionarios e "<<resposta[i][3]<<" canibais     ||      "<<"MARGEM DIREITA: "<<resposta[i][4]<<" missionarios e "<<resposta[i][5]<<" canibais"<<endl;
            break;
        case 1:
            cout<<"MARGEM ESQUERDA: "<<resposta[i][0]<<" missionarios e "<<resposta[i][1]<<" canibais      ||        "<<"------> BARCO: "<<resposta[i][2]<<" missionarios e "<<resposta[i][3]<<" canibais     ||      "<<"MARGEM DIREITA: "<<resposta[i][4]<<" missionarios e "<<resposta[i][5]<<" canibais"<<endl;
            break;
        default:
            cout<<"Nao foi poss�vel encontrar resposta"<<endl;
            break;
        }
        cout<<'\n';
    }
    system("pause");
    return 0;
}