#include
#include
#include
#include
#include
#include
using namespace std;

struct PathUnit
{
int x;
int y;
int direct;
};

class MyMaze
{
vector >vecMaze;
vector >vecMark;
public:
MyMaze(int m,int n):vecMaze(m+2,vector(n+2)),vecMark(m+2,vector(n+2))
{
for(int i = 0; i < m+2; i++)
{
fill(vecMaze[i].begin(),vecMaze[i].end(),1);
}
}

void InitMaze(string strMaze)
{
cout< istringstream in(strMaze);
for(int i = 1; i < vecMaze.size(); i++)
{
for(int j = 1; j < vecMaze[0].size()-1; j++)
{
in>>vecMaze[i][j];
}
}
}

void ShowMaze()
{
for(int i = 0; i < vecMaze.size(); i++)
{
copy(vecMaze[i].begin(),vecMaze[i].end(),ostream_iterator(cout,"\t"));
cout< }
}

void GetNextPath(const PathUnit &cur,PathUnit &next)
{
next = cur;
next.direct = 0;
switch(cur.direct)
{
case 0:
next.x+=1;break;
case 1:
next.y+=1;break;
case 2:
next.x-=1;break;
case 3:
next.y-=1;break;
}
}

bool GetOuter(const PathUnit&u)
{
int out_x = vecMaze[0].size()-2;
int out_y = vecMark.size()-2;

bool bRet = ((u.x==out_x&&u.y==out_y) true:false);
return bRet;
}

void GetPath()
{
stackst;
PathUnit unit;
unit.x=1;
unit.y=1;
unit.direct=0;

st.push(unit);
bool bOver = false;
while(!st.empty())
{
PathUnit cur=st.top();
st.pop();
PathUnit next;
while(cur.direct<=3)
{
GetNextPath(cur,next);
if(GetOuter(next))//横6竖6
{
st.push(cur);
st.push(next);
bOver = true;
break;
}

if(!vecMaze[next.y][next.x]&&!vecMark[next.y][next.x])
{
vecMark[next.y][next.x] = 1;
st.push(cur);
cur= next;
}
else{
cur.direct++;
}
}www.2cto.com
if(bOver)
break;
}
if(bOver)
{
while(!st.empty())
{
PathUnit&u = st.top();
cout<<"("< st.pop();
}
}
else
{
cout<<"this is no paath"< }
}
};

int main()
{
MyMaze m(6,6);
string s = "";
s = s +"0 0 1 0 1 1 "+
"0 1 0 0 1 1 "+
"0 0 0 1 1 1 "+
"1 0 1 1 1 1 "+
"1 0 0 0 0 1 "+
"1 1 1 1 0 0";

m.InitMaze(s);
cout<<"显示迷宫矩阵"< m.ShowMaze();
cout<<"显示路径"< m.GetPath();
return 0;
}