{{{ 
#include <iostream>
#include <fstream>

using namespace std;

const int Max_x = 30;
const int Max_y = 20;

int array[Max_y][Max_x];
/* = 
{
	/*{0,0,1,1,1,1,1,0,0,0,0,0,0,0,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1},
	{1,0,0,0,0,1,1,0,1,1,1,1,1,0,1,1,1,1,0,0,0,0,0,0,1,1,1,1,1,1},
	{1,1,1,1,0,0,0,0,1,1,1,1,1,0,0,0,0,0,0,1,1,1,1,0,0,0,1,1,1,1},
	{1,1,1,1,0,1,1,1,1,1,0,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1},
	{1,1,0,0,0,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1},
	{1,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,1,1},
	{0,0,0,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,0,1,1,1},
	{0,1,1,1,1,1,1,1,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,0,1,1,1},
	{0,1,1,1,0,1,1,1,0,1,1,1,1,1,1,1,0,1,1,1,1,1,1,0,1,1,1,1,1,1},
	{0,0,0,0,0,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1},
	{0,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1},
	{0,1,1,1,1,1,1,1,0,0,0,0,0,0,1,1,1,1,0,1,1,1,0,1,1,1,1,1,1,1},
	{0,0,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,0,1,1,1,0,1,1,1,1,1,1,1},
	{1,0,1,1,1,1,1,1,0,0,0,0,1,1,1,1,1,1,0,0,0,0,0,1,1,1,1,1,1,1},
	{0,0,1,1,1,1,0,1,1,1,1,0,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1},
	{1,1,1,1,1,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1,1,1,1},
	{1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1},
	{1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,1},
	{1,1,1,0,1,1,1,1,0,1,1,1,1,1,1,1,0,1,1,1,1,1,1,0,0,0,0,1,1,1},
	{1,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,1,1,0,0,0,2}

	{0,0,1,1,1,1,1,0,0,0,0,0,0,0,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1},
	{1,0,0,0,0,1,1,0,1,1,1,1,1,0,1,1,1,1,0,0,0,0,0,0,1,1,1,1,1,1},
	{1,1,1,1,0,0,0,0,1,1,1,1,1,0,0,0,0,0,0,1,1,1,1,0,0,0,1,1,1,1},
	{1,1,1,1,0,1,1,1,1,1,0,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1},
	{1,1,0,0,0,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1},
	{1,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,1,1},
	{0,0,0,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,0,1,1,1},
	{0,1,1,1,1,1,1,1,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,0,1,1,1},
	{0,1,1,1,0,1,1,1,0,1,1,1,1,1,1,1,0,1,1,1,1,1,1,0,1,1,0,1,1,1},
	{0,0,0,0,0,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1},
	{0,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,0,1,1,1,1,1,1,1,0,1,1,1},
	{0,1,1,1,1,1,1,1,0,0,0,0,0,0,1,1,1,1,0,1,1,1,0,1,1,1,0,1,1,1},
	{0,0,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,0,1,1,1,0,1,1,1,0,1,1,1},
	{1,0,1,1,1,1,1,1,0,0,0,0,1,1,1,1,1,1,0,0,0,0,0,1,1,1,0,1,1,1},
	{0,0,1,1,1,1,0,1,1,1,1,0,1,1,1,1,1,1,1,1,0,1,1,1,1,1,0,1,1,1},
	{1,1,1,1,1,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,0,0,0,1,1,1,0,1,1,1},
	{1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1},
	{1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,0,1,1,1},
	{1,1,1,0,1,1,1,1,0,1,1,1,1,1,1,1,0,1,1,1,1,1,1,0,0,0,0,1,1,1},
	{1,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,1,1,0,0,0,2}
};*/

void find(int cur, int x, int y);
void show();

//0 길
//1 벽
//2 끝
//3 밟은곳

void main()
{
	int temp[Max_y][Max_x];
	int i, j, k;
	
	ifstream fin("maze.txt");

	for (i = 0; i < Max_y; i++)
	{
		for (j = 0; j < Max_x; j++)
			array[i][j] = fin.get() - '0';
		while (fin.get() != '\n');
	}
	
	for (i = 0; i < 4; i++)
	{
		for (j = 0; j < Max_y; j++)
			for (k = 0; k < Max_x; k++)
				temp[j][k] = array[j][k];
		array[0][0] = 3;
		find(i, 0, 0);						// 처음 위치
		for (j = 0; j < Max_y; j++)
			for (k = 0; k < Max_x; k++)
				array[j][k] = temp[j][k];
	}
}

//0 위
//1 오른
//2 아래
//3 왼

void find(int cur, int x, int y)
{
	int temp[Max_y][Max_x];
	switch (cur)
	{
	case 0 :
		y--;
		break;
	case 1 :
		x++;
		break;
	case 2 :
		y++;
		break;
	case 3 :
		x--;
		break;
	}
	if (x == -1 || x == Max_x || y == -1 || y == Max_y || array[y][x] == 1 || array[y][x] == 3)
		return ;

	if (array[y][x] == 2)
	{
		show();
		return ;
	}

	array[y][x] = 3;
	int i, j, k;
	for (i = 0; i < 4; i++)
	{
		for (j = 0; j < Max_y; j++)
			for (k = 0; k < Max_x; k++)
				temp[j][k] = array[j][k];
		find(i, x, y);
		for (j = 0; j < Max_y; j++)
			for (k = 0; k < Max_x; k++)
				array[j][k] = temp[j][k];
	}
}

void show()
{
	for(int i = 0; i < Max_y; i++)
	{
		for (int j = 0; j < Max_x; j++)
			if (array[i][j] == 3)
				cout << "*";
			else
				cout << array[i][j];
		cout << endl;
	}
	cin.get();
}
}}}