//
//  Canibais.cpp
//  Canibais e Missionarios
//
//  Created by Edvaldo Junior on 08/02/2018.
//  Copyright © 2018 Edvaldo Junior. All rights reserved.
//
//  No problema dos canibais e missionários, três missionários e três canibais devem atravessar um rio
//  com um barco que pode transportar no máximo duas pessoas, sob a restrição de que, para ambas as
//  margens, se há missionários presentes naquela margem, eles não podem ser ultrapassados pelo número
//  de canibais na mesma margem (se fossem, os canibais comeriam os missionários.) O barco não pode
//  atravessar o rio por si só, sem pessoas a bordo.
//
//  O programa resolve o problema de forma geral (para qualquer número nao negativo de missionarios e
//  canibais, além de qualquer número de pessoas suportadas pelo barco). Basta que as constantes
//  MAXMISSIONARIOS, MAXCANIBAIS e MAXBARCO sejam alteradas.
//

#include <bits/stdc++.h>

using namespace std;

#define canibais first
#define missionarios second
#define lado1 first.first
#define lado2 first.second
#define noLado1 true
#define noLado2 false
#define ladoDoBarco second
#define MAXMISSIONARIOS 3
#define MAXCANIBAIS 3
#define MAXBARCO 2

typedef pair<int, int> LadoDoRio;
typedef pair<pair<LadoDoRio, LadoDoRio>, bool> Situacao;

bool visitados[MAXCANIBAIS + 1][MAXMISSIONARIOS + 1][MAXCANIBAIS + 1][MAXMISSIONARIOS + 1][2];
int  distancia[MAXCANIBAIS + 1][MAXMISSIONARIOS + 1][MAXCANIBAIS + 1][MAXMISSIONARIOS + 1][2];
Situacao pais[MAXCANIBAIS + 1][MAXMISSIONARIOS + 1][MAXCANIBAIS + 1][MAXMISSIONARIOS + 1][2];

void iniciaMatrizes();
void buscaSolucao(Situacao, Situacao);
void valores(Situacao, int[4]);
void mostra(Situacao);
void visita(int[4], bool);
void alcancadasPor(Situacao, vector<Situacao>&);
void marcaDistancia(int[4], bool, int);
void marcaPai(int[4], bool, Situacao);
void organizaSolucao(Situacao, Situacao, stack<Situacao>&);
void mostraSolucao(stack<Situacao>);
bool permitido(LadoDoRio);
bool permitido(Situacao);
bool visitou(int[4], bool);
int  pegaDistancia(int[4], bool);
Situacao pegaPai(int[4], bool);

int main () {

    LadoDoRio l1(MAXCANIBAIS, MAXMISSIONARIOS), l2(0, 0),
              idealLado1(0, 0), idealLado2(MAXCANIBAIS, MAXMISSIONARIOS);
    Situacao  inicial(make_pair(l1, l2), noLado1),
              ideal(make_pair(idealLado1, idealLado2), noLado2);

    iniciaMatrizes();
    buscaSolucao(inicial, ideal);

    int val[4];
    valores(ideal, val);
    int d = pegaDistancia(val, ideal.ladoDoBarco);
    if (d != INT_MAX) {
        stack<Situacao> pilha;
        organizaSolucao(inicial, ideal, pilha);
        mostraSolucao(pilha);
    } else { printf("Nao ha solucao!\n"); }

    return 0;
}

void iniciaMatrizes() {

    for (int i = 0; i < MAXCANIBAIS + 1; ++i)
    for (int j = 0; j < MAXMISSIONARIOS + 1; j++)
    for (int k = 0; k < MAXCANIBAIS + 1; k++)
    for (int l = 0; l < MAXMISSIONARIOS + 1; l++)
    for (int m = 0; m < 2; m++) {
        LadoDoRio l1(-1, -1), l2(-1, -1);
        Situacao s(make_pair(l1, l2), noLado1);
        visitados[i][j][k][l][m] = false;
        distancia[i][j][k][l][m] = INT_MAX;
        pais[i][j][k][l][m] = s;
    }
}

void buscaSolucao(Situacao inicial, Situacao ideal) {

    queue<Situacao> fila;
    fila.push(inicial);
    int val[4];
    valores(inicial, val);
    visita(val, inicial.ladoDoBarco);
    marcaDistancia(val, inicial.ladoDoBarco, 0);
    marcaPai(val, inicial.ladoDoBarco, inicial);

    while (!fila.empty()) {
        Situacao atual = fila.front();
        fila.pop();
        valores(atual, val);
        int distanciaA = pegaDistancia(val, atual.ladoDoBarco);

        if (atual == ideal) {
            printf("Conseguiu em %d passos\n", distanciaA);
            break;
        }
        vector<Situacao> alcancadas;
        alcancadasPor(atual, alcancadas);
        visita(val, atual.ladoDoBarco);

        for (auto s : alcancadas) {
            valores(s, val);
            int distanciaS = pegaDistancia(val, s.ladoDoBarco);
            if (!visitou(val, s.ladoDoBarco) && distanciaA + 1 < distanciaS) {
                fila.push(s);
                valores(s, val);
                marcaDistancia(val, s.ladoDoBarco, distanciaA + 1);
                marcaPai(val, s.ladoDoBarco, atual);
            }
        }
    }
}

void valores(Situacao situacao, int val[4]) {

    val[0] = situacao.lado1.canibais;
    val[1] = situacao.lado1.missionarios;
    val[2] = situacao.lado2.canibais;
    val[3] = situacao.lado2.missionarios;
}

void visita(int valores[4], bool lado) {

    int i = lado == noLado1 ? 1 : 0;
    visitados[valores[0]][valores[1]][valores[2]][valores[3]][i] = true;
}

void marcaDistancia(int valores[4], bool lado, int valor) {

    int i = lado == noLado1 ? 1 : 0;
    distancia[valores[0]][valores[1]][valores[2]][valores[3]][i] = valor;
}

int pegaDistancia(int valores[4], bool lado) {

    int i = lado == noLado1 ? 1 : 0;
    return distancia[valores[0]][valores[1]][valores[2]][valores[3]][i];
}

void marcaPai(int valores[4], bool lado, Situacao pai) {

    int i = lado == noLado1 ? 1 : 0;
    pais[valores[0]][valores[1]][valores[2]][valores[3]][i] = pai;
}

void mostra(Situacao situacao) {

    int v[4];
    valores(situacao, v);
    int d = pegaDistancia(v, situacao.ladoDoBarco);
    printf("%12s lado1 lado2 barco passo\n", " ");
    printf("    canibais:  %d     %d   %s   %d\n", v[0], v[2], situacao.ladoDoBarco == noLado1 ?
                                                   "lado1" : "lado2", d);
    printf("missionarios:  %d     %d \n", v[1], v[3]);
    printf("\n");
}

void alcancadasPor(Situacao situacao, vector<Situacao>& v) {

    for (int i = 0; i <= MAXBARCO; i++)
        for (int j = 0; j <= MAXBARCO; j++)
            if (i + j > 0 && i + j <= MAXBARCO) {
                LadoDoRio l1(0, 0), l2(0, 0);
                int a = i, b = j;
                Situacao nova(make_pair(l1, l2), noLado1);
                if (situacao.ladoDoBarco == noLado2) {
                    a *= -1;
                    b *= -1;
                }
                nova.lado1.missionarios = situacao.lado1.missionarios - a;
                nova.lado1.canibais = situacao.lado1.canibais - b;
                nova.lado2.missionarios = situacao.lado2.missionarios + a;
                nova.lado2.canibais = situacao.lado2.canibais + b;
                nova.ladoDoBarco = !situacao.ladoDoBarco;
                if (permitido(nova)) { v.push_back(nova); }
            }
}

bool permitido(LadoDoRio lado) {

    return lado.missionarios == 0 ||
          (lado.missionarios >= lado.canibais &&
           lado.missionarios >= 0 && lado.canibais >= 0 &&
           lado.missionarios <= MAXMISSIONARIOS &&
           lado.canibais <= MAXCANIBAIS);
}

bool permitido(Situacao situacao) {
    return permitido(situacao.lado1) && permitido(situacao.lado2);
}

bool visitou(int valores[4], bool lado) {

    int i = lado == noLado1 ? 1 : 0;
    return visitados[valores[0]][valores[1]][valores[2]][valores[3]][i];
}

Situacao pegaPai(int valores[4], bool lado) {

    int i = lado == noLado1 ? 1 : 0;
    return pais[valores[0]][valores[1]][valores[2]][valores[3]][i];
}

void organizaSolucao(Situacao inicial, Situacao final, stack<Situacao>& pilha) {

    Situacao atual = final;

    while (atual != inicial) {
        pilha.push(atual);
        int val[4];
        valores(atual, val);
        atual = pegaPai(val, atual.ladoDoBarco);
    }
    pilha.push(atual);
}

void mostraSolucao(stack<Situacao> pilha) {

    while (!pilha.empty()) {
        Situacao s = pilha.top();
        pilha.pop();
        mostra(s);
    }
}