/*
Piotr Madej 11K1

Legenda labiryntu:
0 - ściana
1 - ścieżka
2 - wejście
3 - wyjście

---przykład---

21113
01010
01111

Najkrótsze rozwiązanie

2XXX3
01010
01111
*/


#include "stdafx.h"
#include "iostream"
#include "fstream"
#include "string"
#include "windows.h"

using namespace std;

//zdeklarowanie funkcji menu
void menu(int** labirynt, int x, int y, int max);

//zdeklarowanie funkcji animacja
void animacja(int** labirynt, int x, int y, int max);

void main() {
	int x, y=0, z, g, buff, **labirynt, **wyjscia, xp=0,yp=0, elementy=0, element2=0, element3=0, err=0, xw, yw, krok, xb, yb, max;
	char *buff2;
	string nazwa_pliku;
	ifstream plik;

	// petla nieskonczona dopóki nie wczyta sie pliku
	do{
		// plik musi znajdowac sie we folderze razem z program, prosze nie zapomniec o rozszerzeniu
		cout << "podaj nazwe pliku w ktorym znajduje sie labirynt: ";
		cin >> nazwa_pliku;
		plik.open(nazwa_pliku);
	}while(!plik.is_open());

	// sprawdzanie dlugosc pliku
	plik.seekg(0, ios::end);
	buff = plik.tellg();
	plik.seekg(0, ios::beg);

	// tworzenie dynamicznej tablicy na zawartosc pliku
	buff2 = new char[buff];

	// zapisanie danych z pliku do tablicy pomocniczej
	plik.read(buff2,buff);
	buff2[buff] = 0;

	// zamykanie pliku
	plik.close();

	// sprawdzanie liczby kolumn i wierszy labiryntu
	for(z=0; z<buff; z++)
	{
		// kolumn
		if(((buff2[z] == '\r') | (buff2[z] == '\n')) & (y == 0))
		{
			y = z;
		}

		// wierszy
		if(buff2[z] == '3')
		{
			element3++;
			elementy++;
		}

		if(buff2[z] == '2')
		{
			element2++;
			elementy++;
		}

		if((buff2[z] == '1') | (buff2[z] == '0'))
		{
			elementy++;
		}
	}

	if(elementy % y == 0)
	{
		x = elementy/y;

		// deklaruje glowna tablice dynamiczna do przechowywania labiryntu
		labirynt = new int*[x];
		for(z = 0; z < x; z++)
		{
			labirynt[z] = new int[y];
		}

		// wprowadzenie danych do głównej talbicy i walidacja
		for(z=0; z<buff; z++)
		{
			if(buff2[z] == '1' || buff2[z] == '0' || buff2[z] == '2' || buff2[z] == '3')
			{
				if(xp == x)
				{
					cout << "koniec";
					break;
				}

				labirynt[xp][yp] = buff2[z] - '0';
				yp++;

				if(yp == y)
				{
					xp++;
					yp=0;
				}
			}
		}

		// walidacja. jedno wejscie i wyjscia polozone w granicy labiryntu
		for(xp=0; xp < x; xp++)
		{
			for(yp=0; yp < y; yp++)
			{
				if(labirynt[xp][yp] == 2)
				{
					if(!((xp == 0) | (yp == 0) | (xp == (x - 1)) | (yp == (y - 1))))
					{
						cout << "err. wejscie nie znajduje sie w granicy labiryntu\n";
						err = 1;
					}
				}

				if(labirynt[xp][yp] == 3)
				{
					if(!((xp == 0) | (yp == 0) | (xp == (x - 1)) | (yp == (y - 1))))
					{
						cout << "err. wyjscie nie znajduje sie w granicy labiryntu\n";
						err = 1;
					}
				}
			}
		}

		if((element2 != 1) | (element3 < 1))
		{
			cout << "err. za malo/duzo wejsc/wyjsc z labiryntu\n";
			err = 1;
		}

	} else
	{
		cout << "err. niepoprawna struktura labiryntu\n";
		cout << "debug. " << y << "\n" << buff << "\n";
		err = 1;
	}

	if(err != 1)
	{
		cout << "\nwczytano nastepujacy labirynt\n\n";

		for(xp=0; xp < x; xp++)
		{
			for(yp=0; yp < y; yp++)
			{
				cout << labirynt[xp][yp];
			}
			cout << "\n";
		}

		//tworze liste wyjsc
		wyjscia = new int*[x];
		for(z = 0; z < element3; z++)
		{
			wyjscia[z] = new int[2];
		}

		// przerabiam labirynt pod swój algorytm: wyjście=1
		z=0;
		for(xp=0; xp < x; xp++)
		{
			for(yp=0; yp < y; yp++)
			{
				if(labirynt[xp][yp] == 3)
				{
					labirynt[xp][yp] = 1;
					wyjscia[z][0] = xp;
					wyjscia[z][1] = yp;
					z++;
				}
			}
		}

		// algorytm wykonujący kolejno kroki w każdą możliwą stronę zaczynając od wejścia do labiryntu
		krok=1;
		do{
			g=0;
			do{
				z=0;
				for(xp=0; xp < x; xp++)
				{
					for(yp=0; yp < y; yp++)
					{
						if(labirynt[xp][yp] > krok)
						{
							// wykonujemy krok w góre
							if(xp > 0)
							{
								if(labirynt[xp - 1][yp] == 1)
								{
									labirynt[xp - 1][yp] = labirynt[xp][yp] + 1;
									z++;
									g++;
									}
								}

							// wykonujemy krok w lewo
							if(yp > 0)
							{
								if(labirynt[xp][yp - 1] == 1)
								{
									labirynt[xp][yp - 1] = labirynt[xp][yp] + 1;
									z++;
									g++;
								}
							}

							// wykonujemy krok w prawo
							if(yp < (y - 1))
							{
								if(labirynt[xp][yp + 1] == 1)
								{
									labirynt[xp][yp + 1] = labirynt[xp][yp] + 1;
									z++;
									g++;
								}
							}

							// wykonujemy krok w dół
							if(xp < (x - 1))
							{
								if(labirynt[xp + 1][yp] == 1)
								{
									labirynt[xp + 1][yp] = labirynt[xp][yp] + 1;
									z++;
									g++;
								}
							}
						}
					}
				}
			}while(z!=0);
			krok++;
		}while(g!=0);

		buff=labirynt[wyjscia[0][0]][wyjscia[0][1]];
		xw = wyjscia[0][0];
		yw = wyjscia[0][1];

		for(xp=0; xp < element3; xp++)
		{
				if((labirynt[wyjscia[xp][0]][wyjscia[xp][1]] < buff) & (labirynt[wyjscia[xp][0]][wyjscia[xp][1]] != 1))
				{
					buff=labirynt[wyjscia[xp][0]][wyjscia[xp][1]];
					xw = wyjscia[xp][0];
					yw = wyjscia[xp][1];
				}
		}

		// wyświetlenie rozwiązania
		if(labirynt[xw][yw] != 1)
		{
		max = labirynt[xw][yw] - 2;
		cout << "\nliczba krokow potrzebna do przejscia labiryntu wynosi " << max << "\n\n";

		xb = xw;
		yb = yw;

		do{
			buff = labirynt[xb][yb];
			labirynt[xb][yb] = -labirynt[xb][yb];

			for(xp=0; xp < x; xp++)
			{
				for(yp=0; yp < y; yp++)
				{
					if(labirynt[xp][yp] > buff)
					{
						labirynt[xp][yp] = -1;
					}
				}
			}


			if(xb < (x - 1))
			{
				if(labirynt[xb + 1][yb] == buff - 1)
				{
					xb = xb + 1;
					yb = yb;
				}
			}

			if(yb < (y - 1))
			{
				if(labirynt[xb][yb + 1] == buff - 1)
				{
					xb = xb;
					yb = yb + 1;
				}
			}

			if(yb > 0)
			{
				if(labirynt[xb][yb - 1] == buff - 1)
				{
					xb = xb;
					yb = yb - 1;
				}
			}

			if(xb > 0)
			{
				if(labirynt[xb - 1][yb] == buff - 1)
				{
					xb = xb - 1;
					yb = yb;
				}
			}

		}while(labirynt[xb][yb] != 2);

		// bug przy labiryntach gdzie kroków jest jeden lub dwa
		for(xp=0; xp < x; xp++)
		{
			for(yp=0; yp < y; yp++)
			{
				if(labirynt[xp][yp] == 3)
				{
					labirynt[xp][yp] = -1;
				}
			}
		}

		labirynt[xw][yw] = 3;

		for(xp=0; xp < x; xp++)
		{
			for(yp=0; yp < y; yp++)
			{
				if(labirynt[xp][yp] == -1)
				{
					cout << char(248);
				} else
				{
					if(labirynt[xp][yp] < -1)
					{
						cout << char(254);
					} else
					{
						if(labirynt[xp][yp] == 0)
						{
							cout << char(178);
						} else
						{
							cout << labirynt[xp][yp];
						}
					}
				}
			}
			cout << "\n";
		}

		// przechodzimy do menu
		menu(labirynt, x, y, max);

		} else
		{
			cout << "\nbrak rozwiazan labiryntu\n";
		}
	} else
	{
		cout << "prosze poprawic plik z labiryntem i uruchomic program ponownie\n";
	}

	system("pause");
}

// opisanie funkcji menu
void menu(int** labirynt, int x, int y, int max) {
	int xp, yp, menu, koniec=0;
	string nazwa_pliku;
	ofstream zapisz;

	// menu z wyborem
	do{
		cout << "\nMenu. Co chcesz robic?\n";
		cout << "1) Zapisz rozwiazanie labiryntu do pliku\n";
		cout << "2) Wykonaj animacje przechodzenia labiryntu!\n";
		cout << "3) Zamknij program\n";
		cout << "Wybieram: ";
		cin >> menu;
		switch(menu)
		{
		case 1:
			do{
				cout << "podaj nazwe pliku w ktorym mam zapisac rozwiazanie labiryntu: ";
				cin >> nazwa_pliku;
				zapisz.open(nazwa_pliku);
			}while(!zapisz.is_open());

			// tutaj użylem strumieni do zapisywania plikow, nie boje sie o
			for(xp=0; xp < x; xp++)
			{
				for(yp=0; yp < y; yp++)
				{
					if(labirynt[xp][yp] == -1)
					{
						zapisz << "1";
					} else
					{
						if(labirynt[xp][yp] < -1)
						{
							zapisz << "#";
						} else
						{
							zapisz << labirynt[xp][yp];
						}
					}
				}
				zapisz << "\n";
			}
			zapisz.close();
			cout << "Zapisano rozwiazanie do pliku\n";
			break;
		case 2:
			animacja(labirynt, x, y, max);
			break;
		case 3:
			koniec = 1;
			// nie wiem czemu nie można użyć 'break 2;' aby wyjść też z pętli do-while()?
			break;
		}

		if(koniec == 1)
		{
			break;
		}
	}while(1);
}

// opisanie funkcji animacji
void animacja(int** labirynt, int x, int y, int max) {
	int xp, yp, start, **tabanimacja;
	start = 4;
	max = max + 3;
	system("cls");

	tabanimacja = new int*[x];
	for(int z = 0; z < x; z++)
	{
		tabanimacja[z] = new int[y];
	}

	for(xp=0; xp < x; xp++)
	{
		for(yp=0; yp < y; yp++)
		{
			tabanimacja[xp][yp] = labirynt[xp][yp];
		}
	}

	for(xp=0; xp < x; xp++)
	{
		for(yp=0; yp < y; yp++)
		{
			if(tabanimacja[xp][yp] == -1)
			{
				tabanimacja[xp][yp] = 1;
			}

			if(tabanimacja[xp][yp] < 0)
			{
				tabanimacja[xp][yp] = tabanimacja[xp][yp] - 1;
			}

			if(tabanimacja[xp][yp] < 0)
			{
				tabanimacja[xp][yp] = -tabanimacja[xp][yp];
			}
		}
	}
	do{
	for(xp=0; xp < x; xp++)
	{
		for(yp=0; yp < y; yp++)
		{
			if(tabanimacja[xp][yp] > start)
			{
			cout << char(248);
			} else
			{
				if((tabanimacja[xp][yp] == start) | (tabanimacja[xp][yp] > 3))
				{
					cout << char(254);
				} else
				{
					if(tabanimacja[xp][yp] == 0)
					{
						cout << char(178);
					}

					if(tabanimacja[xp][yp] == 1)
					{
						cout << char(248);
					}

					if((tabanimacja[xp][yp] == 2) | (tabanimacja[xp][yp] == 3))
					{
						cout << tabanimacja[xp][yp];
					}
				}
			}
		}
		cout << "\n";
	}

	// bug przy jednym kroku
	if(max == start)
	{
		break;
	}

	start++;
	Sleep(1000);
	if(max != start)
		system("cls");
	}while((max != start));
}