1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstdlib>
 4 #include<cstring>
 5 #include<algorithm>
 6 #include<string>
 7 using namespace std;
 8 int yx[4]={0,1,-1,0};
 9 int yy[4]={1,0,0,-1};
10 int n,m,l;
11 bool vis[30][30];
12 bool c[30][30];
13 int d[200000];
14 struct zb{
15     int l,r;
16 }s[200000][10];
17 int bfs(){
18     int h=0,t=1;
19     d[1]=0;
20     while (h<=t){
21         h++;
22         int x=s[h][1].l,y=s[h][1].r;
23         if (x==1&&y==1) return d[h];
24         memset(c,0,sizeof(c));
25         for (int i=1;i<=l;++i) c[s[h][i].l][s[h][i].r]=1;
26         for (int i=0;i<=3;++i){
27             if (x+yx[i]<=n&&x+yx[i]>=1&&y+yy[i]<=m&&y+yy[i]>=1&&(!vis[x+yx[i]][y+yy[i]])&&(!c[x+yx[i]][y+yy[i]])){
28                 t++;
29                 d[t]=d[h]+1;
30                 s[t][1].l=x+yx[i],s[t][1].r=y+yy[i];
31                 for (int i=2;i<=l;++i) s[t][i].l=s[h][i-1].l,s[t][i].r=s[h][i-1].r;
32             }
33         }
34     }
35     
36 }
37 int main(){
38     freopen ("snake.in","r",stdin);
39     freopen ("snake.out","w",stdout);
40     scanf ("%d%d%d",&n,&m,&l);
41     for (int i=1;i<=l;++i) scanf ("%d%d",&s[1][i].l,&s[1][i].r);
42     int k;
43     scanf ("%d",&k);
44     int x,y;
45     for (int i=1;i<=k;++i) scanf ("%d%d",&x,&y),vis[x][y]=1;
46     printf("%d",bfs());
47     return 0;
48   }

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstdlib>
 4 #include<cstring>
 5 #include<algorithm>
 6 #include<string>
 7 using namespace std;
 8 int yx[4]={1,0,-1,0};
 9 int yy[4]={0,-1,0,1};
10 int n,m,l;
11 bool viss[30][30][1<<15];
12 bool vis[30][30];
13 int lin[20];
14 struct zb{
15     int l,r,z,d;
16 }s[800000];
17 bool check(int x,int y,int s,int p,int q){
18     int i=l-1;
19     for (int i=l-1;i>=1;--i) lin[i]=s&3,s>>=2;
20     for (int i=1;i<l;++i){
21         if (p+yx[lin[i]]==x&&q+yy[lin[i]]==y) return 0;
22         p+=yx[lin[i]],q+=yy[lin[i]];
23     }
24     return 1;
25 }
26 int bfs(){
27     int h=0,t=1;
28     while (h<=t){
29         h++;
30         int x=s[h].l,y=s[h].r,si=s[h].z;
31         viss[x][y][si]=1;
32         if (x==1&&y==1) return s[h].d;
33         for (int i=0;i<=3;++i){
34             if (x+yx[i]<=n&&x+yx[i]>=1&&y+yy[i]<=m&&y+yy[i]>=1&&(!vis[x+yx[i]][y+yy[i]])&&check(x+yx[i],y+yy[i],si,x,y)){
35                 int st=(si>>2)+(((i+2)%4)<<((l-2)*2));
36                 if (viss[x+yx[i]][y+yy[i]][st]) continue;
37                 if (x+yx[i]==1&&y+yy[i]==1) return s[h].d+1;
38                 //cout<<x<<" "<<y<<" "<<si<<" "<<" "<<st<<" "<<i<<endl;
39                 viss[x+yx[i]][y+yy[i]][st]=1;
40                 t++;
41                 s[t].d=s[h].d+1,s[t].z=st;
42                 s[t].l=x+yx[i],s[t].r=y+yy[i];
43             }
44         }
45     }
46     
47 }
48 int main(){
49     freopen ("snake.in","r",stdin);
50     freopen ("snak.out","w",stdout);
51     scanf ("%d%d%d",&n,&m,&l);
52     scanf ("%d%d",&s[1].l,&s[1].r);
53     int xx=s[1].l,yyy=s[1].r;
54     for (int i=2;i<=l;++i){
55         int x,y;
56         scanf ("%d%d",&x,&y);
57         for (int j=0;j<=3;++j){
58             if (xx+yx[j]==x&&yyy+yy[j]==y){
59                 s[1].z=(s[1].z<<2)+j;
60                 break;
61             }
62         }
63         xx=x,yyy=y;
64     }
65     s[1].d=0;
66     int k;
67     scanf ("%d",&k);
68     int x,y;
69     for (int i=1;i<=k;++i) scanf ("%d%d",&x,&y),vis[x][y]=1;
70     printf("%d",bfs());
71     return 0;
72   }