#include <iostream>
#include <stack>
using namespace std;
#define _SIZE_ 10
typedef int Array[_SIZE_][_SIZE_];

struct Pos
{
    int x;
    int y;
    Pos(){}
    Pos(int val1,int val2):x(val1),y(val2){}
};//记录位置x,y，相当于记录的相应位置坐标。
struct Man
{
    Pos pos;
};

class Maze
{
    public:
Maze(int a[][_SIZE_])
    {
        for(int i=0;i<_SIZE_;i++)
        {
            for(int j=0;j<_SIZE_;j++)
            {   
                arr[i][j] = a[i][j];
            }
        }
  }

void Printf()
    {
        for(int i=0;i<_SIZE_;i++)
        {
            for(int j=0;j<_SIZE_;j++)
            {
                cout<<arr[i][j]<<" ";
            }
            cout<<endl;
        }
    }   

 void InitGrial(const Pos &start,const Pos &end)
    {
        Man man;
        man.pos.x = start.x;
        man.pos.y = start.y;
    //  man.kind = RIGHT;
        stack<Man> st;
        stack<Man> sh;
        st.push(man);//此处才把起始位置放进栈st里面。
        Postion(man);//记住man走过的足迹.
        while(!st.empty())
        {
            Pos NewPos;
            Man man = st.top();
            if (InitNewPos(NewPos,man))
            {                   
            Man NewMan;
            NewMan.pos = NewPos;
            st.push(NewMan);
            Postion(NewMan);
            if(NewMan.pos.x==end.x && NewMan.pos.y==end.y)break;
            }
            else
            {
                sh.push(st.top());
                st.pop();
            }
        }   
        while(!sh.empty())
        {
            Man man = sh.top();
            arr[man.pos.x][man.pos.y]=0;
            sh.pop();
        }
    }
    bool InitNewPos(Pos &pos,Man &man)
    {
        if(arr[man.pos.x][man.pos.y+1]==0)
             {
                pos.x=man.pos.x;
                pos.y=man.pos.y+1;
                return true;
             }
        if(arr[man.pos.x+1][man.pos.y]==0)
            {
            pos.x=man.pos.x+1;
            pos.y=man.pos.y;
            return true;
            }
        if(arr[man.pos.x][man.pos.y-1]==0)
            {
            pos.y = man.pos.y-1;
            pos.x = man.pos.x;
            return true;
            }
        if(arr[man.pos.x-1][man.pos.y]==0)
            {
            pos.x = man.pos.x-1;
            pos.y = man.pos.y;
            return true;        
            }
        return false;
    }
    void Postion(Man &man)
    {
        arr[man.pos.x][man.pos.y]=2;
    }
    private:
    Array arr;
};

int main()
{
    int a[][10]=
            {1,0,1,1,1,1,1,1,1,1,
             1,0,0,0,0,0,1,1,0,1,
             1,0,1,1,1,0,0,1,0,1,
             1,0,0,1,1,1,0,0,0,1,
             1,1,0,1,1,1,1,0,0,1,
             1,1,0,1,1,1,1,1,1,1,
             1,1,0,1,1,1,1,1,1,1,
             1,1,0,0,0,0,1,1,1,1,
             1,1,1,1,1,0,0,0,1,1,
       1,1,1,1,1,1,1,0,1,1};        
    Maze ma(a);
    Pos start(0,1);
    Pos end(9,7);//定义开始的位置以及结束的位置。

    ma.InitGrial(start,end);
 //然我们开始吧,实在想不出名字了，Grial是圣杯的意思.

    ma.Printf();    
    return 0;
}