#include <iostream>
#include <iomanip>
using namespace std;
const int Tgt = 110;
const int I = Tgt;
int m[8][8]={
{1,0,0,0,0,0,0,0},
{0,2,0,0,0,0,0,0},
{0,0,0,2,0,0,2,0},
{0,0,0,0,0,0,2,0},
{0,0,0,2,2,0,0,0},
{0,0,0,0,0,0,0,2},
{0,2,2,0,0,0,0,0},
{0,0,0,0,2,0,0,0}
};
struct Coord
{
int x = 0, y = 0;
Coord(int x = 0, int y = 0):x(x),y(y){}
};
const int STOP = 54; //64 - 10;
Coord path[STOP];
bool step(int x, int y, int level)
{
m[x][y] = 1;
if (level == STOP-1)
{
if (x == 0 && y == 1)
{
for(int i = 0; i < level; ++i)
{
cout << "(" << path[i].x << "," << path[i].y << ") - ";
}
cout << "(0,1)\n";
return true;
}
else return false;
}
path[level] = Coord(x,y);
// Up
if (y > 0 && m[x][y-1] == 0)
{
if (step(x,y-1,level+1)) return true;
}
// Dn
if (y < 7 && m[x][y+1] == 0)
{
if (step(x,y+1,level+1)) return true;
}
// Lt
if (x > 0 && m[x-1][y] == 0)
{
if (step(x-1,y,level+1)) return true;
}
// Rt
if (x < 7 && m[x+1][y] == 0)
{
if (step(x+1,y,level+1)) return true;
}
m[x][y] = 0;
return false;
}
int main(int argc, const char * argv[])
{
step(1,0,1);
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8aW9tYW5pcD4KCnVzaW5nIG5hbWVzcGFjZSBzdGQ7Cgpjb25zdCBpbnQgVGd0ID0gMTEwOwpjb25zdCBpbnQgSSAgID0gVGd0OwoKaW50IG1bOF1bOF09ewogICAgezEsMCwwLDAsMCwwLDAsMH0sCiAgICB7MCwyLDAsMCwwLDAsMCwwfSwKICAgIHswLDAsMCwyLDAsMCwyLDB9LAogICAgezAsMCwwLDAsMCwwLDIsMH0sCiAgICB7MCwwLDAsMiwyLDAsMCwwfSwKICAgIHswLDAsMCwwLDAsMCwwLDJ9LAogICAgezAsMiwyLDAsMCwwLDAsMH0sCiAgICB7MCwwLDAsMCwyLDAsMCwwfQp9OwoKc3RydWN0IENvb3JkCnsKICAgIGludCB4ID0gMCwgeSA9IDA7CiAgICBDb29yZChpbnQgeCA9IDAsIGludCB5ID0gMCk6eCh4KSx5KHkpe30KfTsKCmNvbnN0IGludCBTVE9QID0gNTQ7IC8vNjQgLSAxMDsKCkNvb3JkIHBhdGhbU1RPUF07Cgpib29sIHN0ZXAoaW50IHgsIGludCB5LCBpbnQgbGV2ZWwpCnsKICAgIG1beF1beV0gPSAxOwoKICAgIGlmIChsZXZlbCA9PSBTVE9QLTEpCiAgICB7CiAgICAgICAgaWYgKHggPT0gMCAmJiB5ID09IDEpCiAgICAgICAgewogICAgICAgICAgICBmb3IoaW50IGkgPSAwOyBpIDwgbGV2ZWw7ICsraSkKICAgICAgICAgICAgewogICAgICAgICAgICAgICAgY291dCA8PCAiKCIgPDwgcGF0aFtpXS54ICA8PCAiLCIgPDwgcGF0aFtpXS55IDw8ICIpIC0gIjsKICAgICAgICAgICAgfQogICAgICAgICAgICBjb3V0IDw8ICIoMCwxKVxuIjsKICAgICAgICAgICAgcmV0dXJuIHRydWU7CiAgICAgICAgfQogICAgICAgIGVsc2UgcmV0dXJuIGZhbHNlOwogICAgfQoKICAgIHBhdGhbbGV2ZWxdID0gQ29vcmQoeCx5KTsKCiAgICAvLyBVcAogICAgaWYgKHkgPiAwICYmIG1beF1beS0xXSA9PSAwKQogICAgewogICAgICAgIGlmIChzdGVwKHgseS0xLGxldmVsKzEpKSByZXR1cm4gdHJ1ZTsKICAgIH0KICAgIC8vIERuCiAgICBpZiAoeSA8IDcgJiYgbVt4XVt5KzFdID09IDApCiAgICB7CiAgICAgICAgaWYgKHN0ZXAoeCx5KzEsbGV2ZWwrMSkpIHJldHVybiB0cnVlOwogICAgfQogICAgLy8gTHQKICAgIGlmICh4ID4gMCAmJiBtW3gtMV1beV0gPT0gMCkKICAgIHsKICAgICAgICBpZiAoc3RlcCh4LTEseSxsZXZlbCsxKSkgcmV0dXJuIHRydWU7CiAgICB9CiAgICAvLyBSdAogICAgaWYgKHggPCA3ICYmIG1beCsxXVt5XSA9PSAwKQogICAgewogICAgICAgIGlmIChzdGVwKHgrMSx5LGxldmVsKzEpKSByZXR1cm4gdHJ1ZTsKICAgIH0KICAgIG1beF1beV0gPSAwOwogICAgcmV0dXJuIGZhbHNlOwp9CgppbnQgbWFpbihpbnQgYXJnYywgY29uc3QgY2hhciAqIGFyZ3ZbXSkKewoKICAgIHN0ZXAoMSwwLDEpOwp9Cgo=
(0,0) - (1,0) - (2,0) - (2,1) - (2,2) - (1,2) - (1,3) - (1,4) - (2,4) - (2,5) - (3,5) - (3,4) - (3,3) - (3,2) - (3,1) - (3,0) - (4,0) - (4,1) - (4,2) - (5,2) - (5,1) - (5,0) - (6,0) - (7,0) - (7,1) - (7,2) - (7,3) - (6,3) - (5,3) - (5,4) - (6,4) - (6,5) - (7,5) - (7,6) - (7,7) - (6,7) - (6,6) - (5,6) - (5,5) - (4,5) - (4,6) - (4,7) - (3,7) - (2,7) - (1,7) - (0,7) - (0,6) - (1,6) - (1,5) - (0,5) - (0,4) - (0,3) - (0,2) - (0,1)