#include <iostream>
#include <conio.h>
using namespace std;

void PrintMaze();
void wait();
bool FindPath(int pos_x, int pos_y);

const int MAX_X = 10;
const int MAX_Y = 10;

char maze[MAX_Y][MAX_X] = {
	{'x','x','x','x','x','x','x','x','x','x'},
	{'x',' ',' ','x',' ',' ',' ',' ','*','x'},
	{'x',' ',' ',' ',' ','x','x','x','x','x'},
	{'x',' ','x',' ',' ','x',' ',' ',' ','x'},
	{'x',' ','x',' ',' ','x',' ','x','x','x'},
	{'x',' ',' ','x',' ',' ',' ',' ',' ','x'},
	{'x','x',' ',' ',' ','x',' ','x',' ','x'},
	{'x','x',' ','x',' ','x',' ',' ',' ','x'},
	{'x',' ',' ',' ','x','x',' ',' ',' ','x'},
	{'x','x','x','x','x','x','x','x','x','x'}
};

int main() {
	PrintMaze();
	if(FindPath(1,1)) PrintMaze();
	else cout << "\nNo path" << endl;
	wait();
	return 0;
}

void PrintMaze() {
	for(int y = 0; y < MAX_Y; y++) {
		for(int x = 0; x < MAX_X; x++) {
			cout << maze[y][x];
		}
		cout << endl;
	}
}

bool FindPath(int pos_x, int pos_y) {
	bool bln_out = false;

	// Make sure we stay within the limits
	if(pos_x < 0 || pos_x >= MAX_X) bln_out = false;
	else if(pos_y < 0 || pos_y >= MAX_Y) bln_out = false;
	else {

		// The path can't cross a wall ('x') and it can't cross itself
		if(maze[pos_y][pos_x] != 'x' && maze[pos_y][pos_x] != '.' && maze[pos_y][pos_x] != '*') {
			maze[pos_y][pos_x] = '.';
			if(FindPath(pos_x, pos_y + 1)) {
				bln_out = true;
			} else if(FindPath(pos_x, pos_y - 1)) {
				bln_out = true;
			} else if(FindPath(pos_x + 1, pos_y)) {
				bln_out = true;
			} else if(FindPath(pos_x - 1, pos_y)) {
				bln_out = true;
			} else {
				maze[pos_y][pos_x] = ' ';
				bln_out = false;
			}
		// Check to see if we've reached the goal
		} else if(maze[pos_y][pos_x] == '*') {
			bln_out = true;
		} else {
			bln_out = false;
		}
	}
	return bln_out;
}

void wait() {
	int inKey = 0;
	cout << "\nPress any key to continue...";

	do {
		inKey = _getch();
	} while(inKey == 0);
}