//seyed mohammad hoseini
///////////////////////////////////////////////////////////////////

#include <iostream>
#include <time.h>
#include <string>
using namespace std;

void make_new					();					//--------------- clear all locations
void insert_random_blocks		(int);
void insert_block				(int, int);
void insert_mouse				(int, int);
void insert_cheese				(int, int);
void clear						(int, int);			//--------------- clear a location
void print_table				();

void find_way					();
int  find_location				(int);
int  scan_c						(int, int);			//--------------- scan around locaions to find out the cheese
void set_around					(int, int, int);	//--------------- set around locations
void specify_way				();
void find_clear	(int, int);							//--------------- find and clear extra numbers


int location [36][36] = {0};	//	0 : empty	//	-1 : block	//	-2 : mouse	//	-3 : cheese	//
int si=0, sj=0;					// size of i & j
int cx, cy, mx, my;				// coordinate of mouse & cheese
int i,j, counter = 1;
bool ismouse = false, ischeese = false, istable = false;

void main()
{
	cout << "Project #2 : mouse & cheese\n\nfinding the nearest way between mouse and cheese in a table with blocks.\nthe available moves for mouse is left, right, up and down.\n\nprogrammer : \nseyed mohammad hoseini	871412306	hardware\n________________________________________________\n\n\ntype 'help' to show commands list.\n";
	srand ((unsigned) time(0));

	string cmd;

	while (true)
	{
		cout << "\ncommand :>";
		cin >> cmd;
		
		if (cmd == "exit")
		{
			return;
		}
		else if (cmd == "makenewtable")
		{
			cin >> si >> sj;
			if (!(si >= 8 && si <= 35 && sj >= 8 && sj <= 35))
			{
				cout << "the length and width of table must be between 8 and 35\n";
				istable = false;
				si = sj = 0;
				goto EE;
			}
			make_new();
			istable = true;
			cout << "the table created.\n";
		}
		else if (cmd == "insertrandomblocks")
		{
			if (istable == false)
			{
				cout << "there is no table !\n";
				goto EE;
			}
			int b;	//blocks
			cin >> b;
			insert_random_blocks(b);
		}
		else if (cmd == "printtable")
		{
			if (istable == false)
			{
				cout << "there is no table !\n";
				goto EE;
			}
			print_table();
		}
		else if (cmd == "insertblock")
		{
			if (istable == false)
			{
				cout << "there is no table !\n";
				goto EE;
			}
			int x,y;
			cin >> x >> y;
			insert_block(x, y);
		}
		else if (cmd == "insertmouse")
		{
			if (istable == false)
			{
				cout << "there is no table !\n";
				goto EE;
			}
			int x,y;
			cin >> x >> y;
			insert_mouse(x, y);
		}
		else if (cmd == "insertcheese")
		{
			if (istable == false)
			{
				cout << "there is no table !\n";
				goto EE;
			}
			int x,y;
			cin >> x >> y;
			insert_cheese(x, y);
		}
		else if (cmd == "clear")
		{
			if (istable == false)
			{
				cout << "there is no table !\n";
				goto EE;
			}
			int x,y;
			cin >> x >> y;
			clear(x,y);
		}
		else if (cmd == "findway")
		{
			if (istable == false)
			{
				cout << "there is no table !\n";
				goto EE;
			}
			if (ismouse == false)
			{
				cout << "the mouse is not inserted !\n";
				goto EE;
			}
			if (ischeese == false)
			{
				cout << "the cheese is not inserted !\n";
				goto EE;
			}

			find_way();
		}
		else if (cmd == "help")
		{
			cout << "\ncommands : \n\nmakenewtable [length] [width]\nprinttable\ninsertrandomblocks [number of blocks]\ninsertblock [x] [y]\ninsertmouse [x] [y]\ninsertcheese [x] [y]\nclear [x] [y]\nfindway\nhelp\nexit\n\nsample : \n\nmakenewtable 25 20\nprinttable\ninsertrandomblocks 100\ninsertmouse 1 2\ninsertcheese 10 15\nprinttable\nfindway\nprinttable\n\n";
		}
		else
		{
			cout << "invalid command !\ntype 'help' to show commands list.\n";
		}
EE:;
	}
}


void print_table()
{
	int pi,pj;
	cout << "\n";
	for (pj = sj; pj >= 1; pj--)
	{
		if (pj < 10)
			cout << "   " << pj << "  ";
		else
			cout << "  " << pj << "  ";
		for (pi = 1; pi <= si; pi++)
		{
			switch (location [pi][pj])
			{
			case 0:
				cout << ". ";
				break;
			case -1:
				cout << "# ";
				break;
			case -2:
				cout << "M ";
				break;
			case -3:
				cout << "C ";
				break;
			default:	// 1 - 2 - 3 - 4 - 5 - . . .
				cout << "O ";
			}
		}
		cout << "\n";
	}
	cout << "\n      ";
	for (pi = 1; pi <= si; pi++)
	{
		if (pi < 10)
			cout << pi << " ";
		else
			cout << pi;
	}
	cout << "\n      ";
	for (pi = 1; pi <= si; pi++)
		cout << "^ ";
	cout << "\n\n";

}

void make_new ()
{
	ismouse = ischeese = false;
	for (i = 1; i <= 35; i++)
		for (j = 1; j <= 35; j++)
			location [i][j] = 0;
}

void insert_random_blocks(int b)
{
	int x,y;
	for (i = 1; i <= b;)
	{
		x = ((int)((double) rand()/(RAND_MAX + 1) * si)) + 1;
		y = ((int)((double) rand()/(RAND_MAX + 1) * sj)) + 1;
		if(location [x][y] == 0)
		{
			location [x][y] = -1;
			i++;
		}
	}
	cout << b << " random blocks inserted.\n";
}


void insert_block (int x, int y)
{
	if (location [x][y] == 0)
	{
		location [x][y] = -1;
		cout << "the block inserted.\n";
	}
	else
		cout << "the location is not empty !\n";
}

void insert_mouse (int x, int y)
{
	if (ismouse == true)
	{
		cout << "the mouse is already inserted !\n";
		return;
	}
	if (location [x][y] == 0)
	{
		location [x][y] = -2;
		mx = x; my = y;
		ismouse = true;
		cout << "the mouse inserted.\n";
	}
	else
		cout << "the location is not empty !\n";
}

void insert_cheese (int x, int y)
{
	if (ischeese == true)
	{
		cout << "the cheese is already inserted !\n";
		return;
	}
	if (location [x][y] == 0)
	{
		cx = x; cy = y;
		location [x][y] = -3;
		ischeese = true;
		cout << "the cheese inserted.\n";
	}
	else
		cout << "the location is not empty !\n";
}

void clear (int x, int y)
{
	switch (location [x][y])
	{
	case 0:
		cout << "the location was empty.\n";
		break;
	case -1:
		cout << "the block cleared.\n";
		break;
	case -2:
		ismouse = false;
		cout << "the mouse cleared.\n";
		break;
	case -3:
		ischeese = false;
		cout << "the cheese cleared.\n";
		break;
	}
	location [x][y] = 0;
}

void find_way()
{
	counter = 1;
	if (find_location(-2) == 1)
	{
		cout << "\nThe cheese is beside the mouse !\n";
		return;
	}

	while (true)
	{
		if (find_location(counter) == 1)
		{
			break;
		}
		counter += 1;
		if (counter > (si * sj))
		{
			cout << "\nThere is no way !!\n";
			for (i = 1; i <= 35; i++)
				for (j = 1; j <= 35; j++)
					if (location[i][j] != 0 && location[i][j] != -1 && location[i][j] != -2 && location[i][j] != -3)
						location [i][j] = 0;
			return;
		}
	}
	counter += 1;
	specify_way();
	cout << "succeed !\n";
}

int find_location (int f_value)
{
	for (j = 1; j <= sj; j++)
	{
		for (i = 1; i <= si; i++)
		{
			if (location [i][j] == f_value)
			{
				if (scan_c(i,j) == 1)	// scan around the location to find the cheese
				{
					return 1;	//	the cheese is beside the location
				}
				if (f_value == -2)
				{
					set_around(i, j, 1);
				}
				else
				{
					set_around(i, j, f_value + 1);
				}
			}
		}
	}
	return 0;
}

int scan_c (int sx, int sy)
{
	if (sx < si)
	{
		if (location [sx + 1] [sy] == -3)
		{
			return 1;
		}
	}
	if (sx > 1)
	{
		if (location [sx - 1] [sy] == -3)
		{
			return 1;
		}
	}
	if (sy < sj)
	{
		if (location [sx] [sy + 1] == -3)
		{
			return 1;
		}
	}
	if (sy > 1)
	{
		if (location [sx] [sy - 1] == -3)
		{
			return 1;
		}
	}
	return 0;

}

void set_around (int lx, int ly, int s_value)
{
	if (lx < si && location [lx + 1] [ly] == 0)
	{
		location [lx + 1] [ly] = s_value;
	}
	if (lx > 1 && location [lx - 1] [ly] == 0)
	{
		location [lx - 1] [ly] = s_value;
	}
	if (ly < sj && location [lx] [ly + 1] == 0)
	{
		location [lx] [ly + 1] = s_value;
	}
	if (ly > 1 && location [lx] [ly - 1] == 0)
	{
		location [lx] [ly - 1] = s_value;
	}
}


void specify_way ()
{
	for (int reverse_x = cx, reverse_y = cy; counter >= 1; counter--)
	{
		if (reverse_x < si && location [reverse_x + 1] [reverse_y] == counter)
		{
			reverse_x = reverse_x + 1;
			find_clear(reverse_x, reverse_y);
		}
		else if (reverse_x > 1 && location [reverse_x - 1] [reverse_y] == counter)
		{
			reverse_x = reverse_x - 1;
			find_clear(reverse_x, reverse_y);
		}
		else if (reverse_y < sj && location [reverse_x] [reverse_y + 1] == counter)
		{
			reverse_y = reverse_y + 1;
			find_clear(reverse_x, reverse_y);
		}
		else if (reverse_y > 1 && location [reverse_x] [reverse_y - 1] == counter)
		{
			reverse_y = reverse_y - 1;
			find_clear(reverse_x, reverse_y);			
		}
		else
		{
			find_clear (reverse_x, reverse_y);
		}
	}
}

void find_clear(int fx, int fy)
{
	for (j = 1; j <= sj; j++)
	{
		for (i = 1; i <= si; i++)
		{
			if ((location [i][j] == counter) && ((i != fx) || (j != fy)))
			{
				location [i][j] = 0;
			}
		}
	}
}