//老鼠走迷宮
#include<iostream>
#include<conio.h>
#include<windows.h>
using namespace std;

const int MAX_N =10;

int maze[MAX_N][MAX_N] ={
  { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 },
  { 0, 0, 0, 1, 1, 0, 1, 1, 0, 1 },
  { 1, 0, 1, 1, 0, 0, 0, 0, 0, 1 },
  { 1, 0, 0, 0, 0, 1, 0, 1, 0, 1 },
  { 1, 1, 1, 0, 1, 1, 0, 1, 1, 1 },
  { 1, 0, 1, 1, 1, 0, 0, 1, 0, 1 },
  { 1, 0, 0, 0, 0, 0, 1, 1, 0, 0 },
  { 1, 0, 1, 1, 1, 1, 1, 0, 0, 1 },
  { 1, 0, 0, 0, 0, 0, 0, 0, 1, 1 },
  { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }
};

void gotoxy(int x,int y)
{
    SetConsoleCursorPosition (GetStdHandle (STD_OUTPUT_HANDLE),
    (COORD) {2*x , y });
}
void printMap(){
    for(int i=0;i<MAX_N;i++)
    {
        for(int j=0;j<MAX_N;j++){
            gotoxy(i,j);
            if(maze[j][i]==1) cout<<"█";
        }
        cout<<endl;
    }
}

int main(){

    int startX=0,startY=1;
    int x = startX,y = startY;
    int top = 0;
    int data_x[200],data_y[200];

    gotoxy(startX,startY);
    printMap();


    while(1){
        if(x==MAX_N-1)//走到底了，輸出路線圖
        {
            for(int i=top-1;i>=0;i--)
            {
                gotoxy(data_x[i],data_y[i]);
                cout<<"。";
            }
            gotoxy(MAX_N-1,y);
            cout<<"＠";
            gotoxy(0,10);
            cout<<"找到出口了";
            break;
        }

        if(maze[y][x+1]==0)//往右 (若往右走過了 就換方向)
        {
            maze[y][x]=1;//把所佔位置值改為1 表示走過
            data_x[top]=x;//紀錄所佔位置的x座標於stack
            data_y[top]=y;//紀錄所佔位置的y座標於stack
            x++;
            top++;

        }
        else if(maze[y-1][x]==0)//往上
        {
            maze[y][x]=1;
            data_x[top]=x;
            data_y[top]=y;
            y--;
            top++;

        }
        else if(maze[y][x-1]==0)//往左
        {
            maze[y][x]=1;
            data_x[top]=x;
            data_y[top]=y;
            x--;
            top++;

        }
        else if(maze[y+1][x]==0)//往下
        {
             maze[y][x]=1;
             data_x[top]=x;
             data_y[top]=y;
             y++;
             top++;
        }
        else
        {
            maze[y][x]=1;
            top--;
            if(top<0){
                gotoxy(0,10);
                cout<<"迷宮沒出口";
                break;
            }
            x=data_x[top];
            y=data_y[top];
        }
    }
}