#include
void print (int map[][10]); //打印迷宫
void walk (int map[][10], int x, int y); //走迷宫
void push (int x, int *stack); //进栈
void delet (); //出栈
int stackx[100]; //用来存放每一步的x值
int stacky[100]; //每一步的y值
int size = 0; //一共已经走的步数
int walked[10][10]; //已经走过的位置，走过的话值为1，没走过为0
int main (void)
{
int i, j;
int map[10][10];
for (i = 0; i < 10; i++)
{
for (j = 0; j < 10; j++)
{
walked[i][j] = 0;
map[i][j] = ' ';
}
}
for (i = 0, j = 0; j < 10; j++)
map[i][j] = 'o';
for (i = 9, j = 0; j < 10; j++)
map[i][j] = 'o';
for (i = 0, j = 0; i < 10; i++)
map[i][j] = 'o';
for (i = 0, j = 9; i < 10; i++)
map[i][j] = 'o';
map[1][3] = map[2][3] = map[1][7] = map[2][7] = map[3][5] = map[3][6] = map[4][2] = map[4][3] = map[4][4] = map[5][4] = map[6][2] = map[6][6] = map[7][2] = map[7][3] = map[7][4] = map[7][6] = map[7][7] = map[8][1] = 'o';
print (map);
walk (map, 1, 1);
return 0;
}
void print (int map[][10])
{
int i, j;
for (i = 0; i < 10; i++)
{
for (j = 0; j < 10; j++)
printf ("%c", map[i][j]);
printf ("\n");
}
}
void walk (int map[][10], int x, int y)
{
int i;
if (map[x][y] != 'o' && walked[x][y] != 1) //当前位置没有墙并且也没有走过
{
size++;
push (x, stackx);
push (y, stacky);
if (x == 8 && y == 8) //到达终点结束
{
for (i = 0; i < size; i++)
printf ("%d %d\n", stackx[i], stacky[i]);
return;
}
}
else //位置不可通，判断栈顶位置是否还有其他方向未探索
{
if (size != 0 && walked[stackx[size-1]+1][stacky[size-1]] != 1 && map[stackx[size-1]+1][stacky[size-1]] != 'o' && stackx[size-1]+1 <= 9 && stackx[size-1]+1 >= 0)
{
x = stackx[size-1] + 1;
y = stacky[size-1];
walked[x][y] = 1;
walk (map, x, y);
}
else if (size != 0 && walked[stackx[size-1]][stacky[size-1] + 1] != 1 && map[stackx[size-1]][stacky[size-1] + 1] != 'o' && stacky[size-1] + 1 <= 9 && stacky[size-1] + 1 >= 0)
{
x = stackx[size-1];
y = stacky[size-1] + 1;
walked[x][y] = 1;
walk (map, x, y);
}
else if (size != 0 && walked[stackx[size-1]-1][stacky[size-1]] != 1 && map[stackx[size-1]-1][stacky[size-1]] != 'o' && stackx[size-1]-1 <= 9 && stackx[size-1]-1 >= 0)
{
x = stackx[size-1]-1;
y = stacky[size-1];
walked[x][y] = 1;
walk (map, x, y);
}
else if (size != 0 && walked[stackx[size-1]][stacky[size-1]-1] != 1 && map[stackx[size-1]][stacky[size-1]-1] != 'o' && stacky[size-1]-1 >= 0 && stacky[size-1]-1 <= 9)
{
x = stackx[size-1];
y = stacky[size-1]-1;
walked[x][y] = 1;
walk (map, x, y);
}
else //如果全探索了，就删去栈顶位置
{
delet ();
if (size == 0)
return;
walk(map, x, y);
}
}
}
void push (int x, int *stack)
{
stack[size-1] = x;
}
void delet ()
{
size--;
}
