# 5.2.1 Snail Trails 蜗牛的旅行

5.2.1 Snail Trails 蜗牛的旅行

```
A B C D E F G H
1 S . . . . . # .
2 . . . . # . . .
3 . . . . . . . .
4 . . . . . . . .
5 . . . . . # . .
6 # . . . . . . .
7 . . . . . . . .
8 . . . . . . . .
```

```
A B C D E F G H
1 S---------+ # .
2 . . . . # | . .
3 . . . . . | . .
4 . . . . . +---+
5 . . . . . # . |
6 # . . . . . . |
7 +-----------+ |
8 +-------------+

```

``````8 4
E2
A6
G1
F5 ``````

``33``

``````#include <iostream>
using namespace std;

int n,b;
bool mat[125][125];
bool isvis[125][125];
bool isvisd[125][125][4];
int row[4] = {0,0,-1,1};
int col[4] = {-1,1,0,0};
int rol[4][2] = {{2,3},{2,3},{0,1},{0,1}};
int res;

void dfs(int x, int y, int t, int d)
{
int i,cx,cy,cd;
cx = x+row[d];
cy = y+col[d];
if(cx >= 1 && cx <= n && cy >=1 && cy <= n)
{
if(isvis[cx][cy] == true)
{
if(res < t)
res = t;
}
else
{
if(mat[cx][cy] == false)
{
isvis[cx][cy] = true;
dfs(cx,cy,t+1,d);
isvis[cx][cy] = false;
}
else
{
cx = x;
cy = y;
isvisd[cx][cy][d] = true;
for(i = 0; i < 2; i++)
{
cd = rol[d][i];
if(isvisd[cx][cy][cd] == false)
dfs(cx,cy,t,cd);
}
isvisd[cx][cy][d] = false;
}
}
}
else
{
cx = x;
cy = y;
isvisd[cx][cy][d] = true;
for(i = 0; i < 2; i++)
{
cd = rol[d][i];
if(isvisd[cx][cy][cd] == false)
dfs(cx,cy,t,cd);
}
isvisd[cx][cy][d] = false;
}
}

int main()
{
int i;
char col;
int row;
cin >> n >> b;
for(i = 1; i <= b; i++)
{
cin >> col >> row;
mat[row][col-'A'+1] = true;
}
res = 1;
isvis[1][1] = true;
dfs(1,1,1,1);
dfs(1,1,1,3);
cout << res << endl;
return 0;
} ``````

``````#include <iostream>
using namespace std;

int n,b;
bool mat[125][125];
bool isvis[125][125];
bool isvisd[125][125][4];
int row[4] = {0,0,-1,1};
int col[4] = {-1,1,0,0};
int rol[4][2] = {{2,3},{2,3},{0,1},{0,1}};
int res;

void dfs(int x, int y, int t, int d)
{
int i,cx,cy,cd;
cx = x+row[d];
cy = y+col[d];
if(cx >= 1 && cx <= n && cy >=1 && cy <= n)
{
if(isvis[cx][cy] == true)
{
if(res < t)
res = t;
}
else
{
if(mat[cx][cy] == false)
{
isvis[cx][cy] = true;
dfs(cx,cy,t+1,d);
isvis[cx][cy] = false;
}
else
{
cx = x;
cy = y;
isvisd[cx][cy][d] = true;
for(i = 0; i < 2; i++)
{
cd = rol[d][i];
if(isvisd[cx][cy][cd] == false)
dfs(cx,cy,t,cd);
}
isvisd[cx][cy][d] = false;
}
}
}
else
{
cx = x;
cy = y;
isvisd[cx][cy][d] = true;
for(i = 0; i < 2; i++)
{
cd = rol[d][i];
if(isvisd[cx][cy][cd] == false)
dfs(cx,cy,t,cd);
}
isvisd[cx][cy][d] = false;
}
}

int main()
{
int i;
char col;
int row;
cin >> n >> b;
for(i = 1; i <= b; i++)
{
cin >> col >> row;
mat[row][col-'A'+1] = true;
}
res = 1;
isvis[1][1] = true;
dfs(1,1,1,1);
dfs(1,1,1,3);
cout << res << endl;
return 0;
} ``````