#include <cstdio>
#include <deque>
#include <windows.h>
using
namespace
std;
class
node
{
public
:
int
x,y;
int
lastOpt;
};
deque<node> sta;
int
x,y;
int
endx,endy;
int
mapW,mapH;
int
steps;
int
xopt[5]= {0,0,1,0,-1};
int
yopt[5]= {0,1,0,-1,0};
int
map[100][100]=
{
};
void
init()
{
x = 1;
y = 1;
endx = 1;
endy = 9;
mapH = 10;
mapW = 10;
for
(
int
i=0; i<=mapH; i++)
for
(
int
j=0; j<=mapW; j++)
{
if
(i==0 ||j==0 ||i==mapH||j==mapW)
map[i][j]=-1;
}
steps=0;
map[1][2]=-1;
map[2][2]=-1;
map[3][2]=-1;
map[4][2]=-1;
map[6][2]=-1;
map[7][2]=-1;
map[8][2]=-1;
map[9][2]=-1;
map[9][3]=-1;
map[8][3]=-1;
map[1][4]=-1;
map[3][4]=-1;
map[4][4]=-1;
map[5][4]=-1;
map[6][4]=-1;
map[7][4]=-1;
map[1][6]=-1;
map[2][6]=-1;
map[3][6]=-1;
map[4][6]=-1;
map[5][6]=-1;
map[6][6]=-1;
map[7][6]=-1;
map[8][6]=-1;
map[8][7]=-1;
map[8][8]=-1;
map[7][8]=-1;
map[6][8]=-1;
map[5][8]=-1;
map[4][8]=-1;
map[3][8]=-1;
map[2][8]=-1;
map[1][8]=-1;
map[endx][endy]=5;
}
void
dis()
{
system
(
"cls"
);
int
ori = map[x][y];
map[x][y]=1;
for
(
int
i=0; i<=mapH; ++i)
{
for
(
int
j=0; j<=mapW; ++j)
{
if
(map[i][j]==0)
printf
(
" "
);
else
if
(map[i][j]==-1)
printf
(
" #"
);
else
if
(map[i][j]==1)
printf
(
" @"
);
else
if
(map[i][j]==2)
printf
(
" ."
);
else
if
(map[i][j]==5)
printf
(
" !"
);
}
cout<<i<<endl;
}
for
(
int
j=0; j<=mapW; ++j)
cout<<j<<
" "
;
printf
(
"\n\n > steps:%d Exit:(%d,%d)\n"
,steps,endx,endy);
map[x][y] = ori;
}
int
can(
int
n)
{
if
(map[x+xopt[n]][y+yopt[n]] == 0 || map[x+xopt[n]][y+yopt[n]] == 5)
return
1;
return
0;
}
void
visit(
int
n)
{
map[x][y]=2;
x+=xopt[n];
y+=yopt[n];
node tem;
tem.x = x;
tem.y = y;
tem.lastOpt = n;
sta.push_back(tem);
steps++;
}
int
main()
{
init();
node tem;
while
( x != endx || y!=endy)
{
int
cans = 0;
for
(
int
i=1; i<=4; i++)
{
if
(can(i))
{
cans = 1;
visit(i);
break
;
}
}
if
(!cans)
{
if
(!sta.empty())
{
tem = sta.back();
map[tem.x][tem.y]=0;
sta.pop_back();
}
else
{
map[x][y]=2;
x+=xopt[tem.lastOpt];
x+=yopt[tem.lastOpt];
dis();
break
;
}
}
dis();
Sleep(500);
}
if
(x==endx && y == endy)
cout<<
"\n > i am finished....\n"
;
else
cout<<
"\n > i am finished...but i can't find the right way\n"
;
return
0;
}