/*
 这个也是大一下学期写的
 当时不太会用结构体
 所以代码显得比较weak。。。
 后来说要做个改进
 一直也没有付诸实施
 */
#include<stdio.h>
#include<string.h>

int x[1000], y[1000], p[1000], m[1000], n[1000], *topm, *topn, *topx, *topy,
		*topp, *basem, *basen, *basex, *basey, *basep;
int l, r;
char a[100][100];

void Initstackx()
{
	topx = basex = x;
}
void Initstacky()
{
	topy = basey = y;
}
void Initstackp()
{
	topp = basep = p;
}

void Initstackm()
{
	topm = basem = m;
}
void Initstackn()
{
	topn = basen = n;
}

int stackemptyx()
{
	if (topx == basex)
		return (1);
	else
		return (0);
}
int stackemptyy()
{
	if (topy == basey)
		return (1);
	else
		return (0);
}
int stackemptyp()
{
	if (topp == basep)
		return (1);
	else
		return (0);
}

int* gettopx()
{
	return (topx);
}
int* gettopy()
{
	return (topy);
}
int* gettopp()
{
	return (topp);
}

int* popx()
{
	topx--;
	return (topx + 1);
}
int* popy()
{
	topy--;
	return (topy + 1);
}
int* popp()
{
	topp--;
	return (topp + 1);
}

void pushx(int pos)
{
	topx++;
	*topx = pos;
}
void pushy(int pos)
{
	topy++;
	*topy = pos;
}
void pushp(int pos)
{
	topp++;
	*topp = pos;
}

void pushm(int pos)
{
	topm++;
	*topm = pos;                                                         //
}
void pushn(int pos)
{
	topn++;
	*topn = pos;
}

int check(int i, int j)
{
	int *p1, *p2;
	p1 = basem + 1;
	p2 = basen + 1;
	while (p1 <= topm)
	{
		if (*p1 == i && *p2 == j)
			return (1);
		else
		{
			p1++;
			p2++;
		}
	}
	return (0);
}
int rout(int i, int j, int pos)
{
	switch (pos)
	{
	case 0:
		if (a[i][j + 1] != '#' && j + 1 < l && check(i, j + 1) != 1)
			return (1);
		else if (a[i + 1][j] != '#' && i + 1 < r && check(i + 1, j) != 1)
			return (2);
		else if (a[i][j - 1] != '#' && j - 1 >= 0 && check(i, j - 1) != 1)
			return (3);
		else if (a[i - 1][j] != '#' && i - 1 >= 0 && check(i - 1, j) != 1)
			return (4);
		else
			return (0);
	case 1:
		if (a[i + 1][j] != '#' && i + 1 < r && check(i + 1, j) != 1)
			return (2);
		else if (a[i][j - 1] != '#' && j - 1 >= 0 && check(i, j - 1) != 1)
			return (3);
		else if (a[i - 1][j] != '#' && i - 1 >= 0 && check(i - 1, j) != 1)
			return (4);
		else
			return (0);
	case 2:
		if (a[i][j + 1] != '#' && j + 1 < l && check(i, j + 1) != 1)
			return (1);
		else if (a[i][j - 1] != '#' && j - 1 >= 0 && check(i, j - 1) != 1)
			return (3);
		else if (a[i - 1][j] != '#' && i - 1 >= 0 && check(i - 1, j) != 1)
			return (4);
		else
			return (0);
	case 3:
		if (a[i][j + 1] != '#' && j + 1 < l && check(i, j + 1) != 1)
			return (1);
		else if (a[i + 1][j] != '#' && i + 1 < r && check(i + 1, j) != 1)
			return (2);
		else if (a[i - 1][j] != '#' && i - 1 >= 0 && check(i - 1, j) != 1)
			return (4);
		else
			return (0);
	case 4:
		if (a[i][j + 1] != '#' && j + 1 < l && check(i, j + 1) != 1)
			return (1);
		else if (a[i + 1][j] != '#' && i + 1 < r && check(i + 1, j) != 1)
			return (2);
		else if (a[i][j - 1] != '#' && j - 1 >= 0 && check(i, j - 1) != 1)
			return (3);
		else
			return (0);
	}
}

int main()
{
	puts(
			"**********************************************************************");
	puts(
			"*                                                                    *");
	puts("*                走              迷             宫                   *");
	puts(
			"*                                                                    *");
	puts("*                       软件2班      王凯旋                          *");
	puts(
			"**********************************************************************\n\n");
	puts("说明：1 . 以'#'代表墙，空格代表可走区域");
	puts("      2 . 可走任意阶迷宫，'CTRL + Z'代表输入结束");
	puts("      3 . 不必输入边框");
	int i, j, t;
	begin: Initstackx();
	Initstacky();
	Initstackp();
	Initstackm();
	Initstackn();
	gets(a[0]);
	if ((l = strlen(a[0])) == 0)
	{
		printf("您没有输入迷宫\n请输入迷宫：\n");
		goto begin;
	}
	r = 1;
	while (gets(a[r]))
		r++;                              //得到迷宫
	i = 0;
	j = 0;
	while (1)
	{
		pushm(i);
		pushn(j);
		if (i == r - 1 && j == l - 1)
		{                          //到出口位置跳出
			if (a[i][j] == '#')
				goto out;
			else
				goto output;
		}
		if ((t = rout(i, j, 0)) > 0)                        //当前位置可通     t为可通方向
		{
			pushx(i);
			pushy(j);
			pushp(t);                                    //路径进栈
			switch (t)
			//切换下一个位置为当前位置
			{
			case 1:
				j++;
				break;
			case 2:
				i++;
				break;
			case 3:
				j--;
				break;
			case 4:
				i--;
				break;
			}
		}
		else                                            //当前位置不可通
		{
			if ((!stackemptyx())
					&& ((t = rout(*gettopx(), *gettopy(), *gettopp()) > 0))) //栈不空且上一个位置还有其他路径可走
			{
				popp();
				pushp(t);                         //压入新位置
				switch (t)
				//切换到下一个当前位置
				{
				case 1:
					j++;
					break;
				case 2:
					i++;
					break;
				case 3:
					j--;
					break;
				case 4:
					i--;
					break;
				}
			}
			else
			{
				while ((!stackemptyx())
						&& ((t = rout(*gettopx(), *gettopy(), *gettopp())) == 0)) //当栈不空且当前位置无其他路可走
				{
					popx();
					popy();
					popp();
					i = *gettopx();
					j = *gettopy();
				}                          //弹出当前位置
				if (stackemptyx())               //若栈空，跳出
					goto out;
				else                               //否则切换下一个当前位置
				{
					popp();
					pushp(t);                        //压入新位置
					switch (t)
					//切换到下一个当前位置
					{
					case 1:
						j++;
						break;
					case 2:
						i++;
						break;
					case 3:
						j--;
						break;
					case 4:
						i--;
						break;
					}
				}
			}
		}
	}
	out: if (stackemptyx())
	{
		puts("No solution!\n");
		goto begin;
	}
	output: putchar(10);
	while (!stackemptyx())
	{
		a[*popx()][*popy()] = '.';
	}
	a[r - 1][l - 1] = '.';
	for (i = 0; i < l + 2; i++)
		printf("0");
	printf("\n");
	for (i = 0; i < r; i++)
	{
		printf("0");
		for (j = 0; j < l; j++)
			printf("%c", a[i][j]);
		printf("0\n");
	}
	for (i = 0; i < l + 2; i++)
		printf("0");
	printf("\n");
	goto begin;
}