Misionari si canibali

#pragma warning(disable:4996)
#include <stdio.h>
#include <string.h>
#include <conio.h>

struct alfabet {
	int m, c, b;
};
struct alfabet noduri[20], nod, Vizitate[20], parinte[20], solutie[20];

bool conditie_vizitate(int nr_vizitate, struct alfabet aux) {          // Testeaza daca dupa mutarea respectiva s-a ajuns la o stare anterioara
	for (int i = 0; i < nr_vizitate; i++)
		if (aux.b == 0) {    // daca suntem pe primul mal
			if ((aux.m == Vizitate[i].m) && (aux.c == Vizitate[i].c) && (aux.b == Vizitate[i].b))
				return false;
		}
		else                // daca suntem pe al doilea mal
			if ((3 - aux.m == Vizitate[i].m) && (3 - aux.c == Vizitate[i].c) && (aux.b == Vizitate[i].b))
				return false;
	return true;
}

bool conditii_necesare(int nr_vizitate, struct alfabet aux) {           // Testeaza daca se poate face mutarea respecti
																		// Primele doua conditii pe primul mal sa fie mai multi misionari decat canibali sau sa nu fie niciun misionar
																		// A treia si a patra conditie sa avem mai multi misionari si canibali decat 0dupa mutarea respectiva se verifica daca s-a ajuns la o stare anterioara
																		// A cincea conditie dupa mutarea respectiva se verifica daca s-a ajuns la o stare anterioara
																		// A sasea si saptea conditie pe malul opus sa avem mai multi misionari decat canibali sau sa nu avem niciun misionar
																		// A opta si a noua conditie pe malul opus sa avem mai multi misionari si canibali decat 0
	if (((aux.m >= aux.c) || (aux.m == 0)) && (aux.m >= 0) && (aux.c >= 0) && (conditie_vizitate(nr_vizitate, aux) == true) &&
		((3 - aux.m >= 3 - aux.c) || (3 - aux.m == 0)) && ((3 - aux.m >= 0) && (3 - aux.c >= 0)))
		return true;
	return false;
}

void adaugare_in_noduri(struct alfabet aux, int &nr_noduri, int &nr_vizitate) {     // Daca se poate face mutarea respectiva se adauga in noduri si in Vizitate si se retine parintele
	if (aux.b == 0) {   // daca suntem pe primul mal
		Vizitate[nr_vizitate++] = noduri[nr_noduri++] = aux;
	}
	else {           // daca suntem pe al doilea mal
		Vizitate[nr_vizitate].m = noduri[nr_noduri].m = 3 - aux.m;
		Vizitate[nr_vizitate].c = noduri[nr_noduri].c = 3 - aux.c;
		Vizitate[nr_vizitate++].b = noduri[nr_noduri++].b = 1;
	}
	parinte[nr_vizitate - 1] = nod;
}

void afisare_mutare_urmatoare(int i) {    // Pentru a afisa mutarile pe care le face algoritmul la final
	if (((solutie[i - 1].m - 1 == solutie[i].m) &&
		(solutie[i - 1].c - 1 == solutie[i].c)) || ((solutie[i - 1].m + 1 == solutie[i].m) &&
		(solutie[i - 1].c + 1 == solutie[i].c)))
		printf("1misionar si 1canibal");
	if (((solutie[i - 1].m - 1 == solutie[i].m) || (solutie[i - 1].m + 1 == solutie[i].m)) &&
		(solutie[i - 1].c == solutie[i].c))
		printf("1misionar");
	if (((solutie[i - 1].m - 2 == solutie[i].m) || (solutie[i - 1].m + 2 == solutie[i].m)) &&
		(solutie[i - 1].c == solutie[i].c))
		printf("2misionari");
	if (((solutie[i - 1].c - 1 == solutie[i].c) || (solutie[i - 1].c + 1 == solutie[i].c)) &&
		(solutie[i - 1].m == solutie[i].m))
		printf("1canibal");
	if (((solutie[i - 1].c - 2 == solutie[i].c) || (solutie[i - 1].c + 2 == solutie[i].c)) &&
		(solutie[i - 1].m == solutie[i].m))
		printf("2canibali");
}
void rezolva() {
	int sol = 0, nr_noduri = 0, nr_vizitate = 0, barca, nr_parinte = 0;

	Vizitate[0].m = Vizitate[0].c = 3;           // Initializarea datelor initiale in noduri si Vizitate cu 3m 3c 1
	Vizitate[nr_vizitate++].b = 1;
	noduri[nr_noduri].m = noduri[nr_noduri].c = 3;
	noduri[nr_noduri++].b = 1;
	while (sol == 0) {
		nod = noduri[0];
		barca = nod.b;
		for (int i = 1; i < nr_noduri; i++)
			noduri[i - 1] = noduri[i];
		nr_noduri--;
		if ((nod.m == 0) && (nod.c == 0) && (nod.b == 0))
			sol = 1;
		else {
			struct alfabet aux = nod;
			if (barca == 1)                // Daca barca=1 suntem pe primul mal, daca barca=0 suntem pe al doilea mal
				aux.b = 0;
			else
				aux.b = 1;
			if (aux.b == 1) {              // Daca suntem pe al doilea mal dam valorile de pe malul respectiv ex: (3,2,0) inseamna ca pe malul al doilea avem 3-3=0m 3-2=1c (0,1,0)
				aux.m = 3 - aux.m;
				aux.c = 3 - aux.c;
			}
			aux.m--;
			if (conditii_necesare(nr_vizitate, aux) == true)        // Se testeaza daca se poate muta 1m
				adaugare_in_noduri(aux, nr_noduri, nr_vizitate);   // Se adauga in noduri si Vizitat situatia dupa mutare

			aux.m++;
			aux.m = aux.m - 2;
			if (conditii_necesare(nr_vizitate, aux) == true)     // Se testeaza daca se pot muta 2m
				adaugare_in_noduri(aux, nr_noduri, nr_vizitate);

			aux.m = aux.m + 2;
			aux.c--;
			if (conditii_necesare(nr_vizitate, aux) == true)    // Se testeaza daca se poate muta 1c
				adaugare_in_noduri(aux, nr_noduri, nr_vizitate);

			aux.c++;
			aux.c = aux.c - 2;
			if (conditii_necesare(nr_vizitate, aux) == true)   // Se testeaza daca se pot muta 2c
				adaugare_in_noduri(aux, nr_noduri, nr_vizitate);

			aux.c = aux.c + 2;
			aux.c--;
			aux.m--;
			if (conditii_necesare(nr_vizitate, aux) == true)   // Se testeaza daca se poate muta 1m si 1c
				adaugare_in_noduri(aux, nr_noduri, nr_vizitate);
		}
	}

	int n = 0;

	solutie[n++] = Vizitate[nr_vizitate - 1];   // Initializam solutia cu (0,0,0)
	while ((solutie[n - 1].m != 3) || (solutie[n - 1].c != 3) || (solutie[n - 1].b != 1)) {   // Parcurgem in mod invers de la final la inceput
		int i = 0;
		while ((solutie[n - 1].m != Vizitate[i].m) || (solutie[n - 1].c != Vizitate[i].c) || (solutie[n - 1].b != Vizitate[i].b))  // Cautam parintele nodului solutie[n-1]
			i++;
		solutie[n++] = parinte[i];  // Introducem parintele in solutie si continuam pana ajungem la inceput( (3,3,1) )
	}
	for (int i = n - 1; i >= 0; i--) {  // Afisam solutia
		printf("Starea curenta: (%dm,%dc,%d) \n", solutie[i].m, solutie[i].c, solutie[i].b);
		printf("Mutarea urmatoare: ");
		afisare_mutare_urmatoare(i);
		printf("\n\n");
	}
}

void main() {

	rezolva();
	_getch();
}