题解：

练代码功底的题目

首先思路嘛很显然 spfa+状压dp（你要说爆搜也可以）

令f[i][j][s][k]表示当前在i，j，蛇的形状为s，然后吃到的状态是k

然后呢细节一大堆

首先空间就是个问题

12*12*2^12*2^4

（为什么是2^14次方呢 因为可以记录相邻之间的关系有4种，然后最多要记录6个，我代码里写的是7个。。最后一次的那个是不用记得）

然后还要输出方案 如果是记6个的话应该可以随便开

如果记7个的话 那就搞一个int记录前面蛇的状态，两个bool记录蛇的位置（因为只有1-4）

然后颜色是要当时算的

这样勉强512mb卡过去。。

时间上嘛理论是（x=12*12*2^12*2^4） xlogx的

但因为挺多状态是冗余的 应该是够得。。

然后我觉得洛谷上的评测可能是单一答案么。。。 所以只拿了no solution的分

以后再看看。。

代码：

#include 
     
      using namespace std;#define maxn1 16390#define maxn2 15int dp[13][13][maxn1][maxn2],w[16][16],ft[16][16];int pre[13][13][maxn1][maxn2];bool pre2[3][13][13][maxn1][maxn2];bool ff[16][16][maxn1][maxn2];int dx[5]={
   0,1,-1,0,0};int dy[5]={
   0,0,0,1,-1};int n,m,k;int jl[1000000];struct re{    int a,b,c,d;};queue
      
        q;int js(int x,int y,int x1,int y1){    if (x1==x+1) return(0);    if (x1==x-1) return(3);    if (y1==y+1) return(2);    if (y1==y-1) return(1);}int query(int x){    int cnt=4;    for (int i=1;i<=4;i++)      if (x>>i&1) cnt++;    return(cnt);}bool pd(re tmp,int i){    int x=tmp.a,y=tmp.b,now=tmp.c;    int x1=x+dx[i],y1=y+dy[i];    if (x1<=0||y1<=0||x1>n||y1>m||w[x1][y1]==0) return(false);     int len=query(tmp.d);    for (int i=1;i
       
        >2)<<2);        now>>=2;        if (tmp==0) x++;        if (tmp==3) x--;        if (tmp==2) y++;        if (tmp==1) y--;        if (x1==x&&y1==y) return(false);    }    return(true);}re js2(re tmp,int i){    int x=tmp.a,y=tmp.b;    if (ft[x+dx[i]][y+dy[i]])    {        int x1,x2=tmp.d|(1<<(ft[x+dx[i]][y+dy[i]]-1));        x1=(tmp.c<<2)+js(x+dx[i],y+dy[i],x,y);        re x3={x1,x2};        return(x3);    }    int now=tmp.c,cnt=0,len=query(tmp.d);    for (int j=1;j
        
         >=2;        cnt+=2;    }    re x3={((tmp.c-(now<
         
          <<2)+js(x+dx[i],y+dy[i],x,y),tmp.d};    return(x3);}char c[100];#define INF 1e9int main(){    freopen("noi.in","r",stdin);    freopen("noi.out","w",stdout);    std::ios::sync_with_stdio(false);    cin>>n>>m;    for (int i=1;i<=n;i++)    {        cin>>c;        for (int j=1;j<=m;j++) w[i][j]=c[j-1]-'0';    }    int x,y,x2,y2;    cin>>x>>y; x2=x; y2=y; int tmp=0;    for (int i=1;i<=3;i++)    {        int x1,y1;        cin>>x1>>y1;        tmp+=js(x,y,x1,y1)<<(2*(i-1));        x=x1; y=y1;    }    memset(dp,-1,sizeof(dp));    dp[x2][y2][tmp][0]=0;    pre[x2][y2][tmp][0]=-1;    re x4={x2,y2,tmp,0}; q.push(x4);    cin>>k;    for (int i=1;i<=k;i++)    {        int x,y;        cin>>x>>y;        ft[x][y]=i;    }    int goal=(1<
          
           ans) continue; for (int i=1;i<=4;i++) if (pd(x,i)) { re r=js2(x,i); if (dp[x.a][x.b][x.c][x.d]+abs(w[x.a+dx[i]][x.b+dy[i]]-w[x.a][x.b])+1
           
            >1; pre2[2][x.a+dx[i]][x.b+dy[i]][r.a][r.b]=(i-1)&1; pre[x.a+dx[i]][x.b+dy[i]][r.a][r.b]=x.c; dp[x.a+dx[i]][x.b+dy[i]][r.a][r.b]= dp[x.a][x.b][x.c][x.d]+abs(w[x.a+dx[i]][x.b+dy[i]]-w[x.a][x.b])+1; re tmp=re{x.a+dx[i],x.b+dy[i],r.a,r.b}; if (r.b!=goal&&ff[x.a+dx[i]][x.b+dy[i]][r.a][r.b]) { q.push(tmp); ff[x.a+dx[i]][x.b+dy[i]][r.a][r.b]=0; } if (r.b==goal&&dp[x.a+dx[i]][x.b+dy[i]][r.a][r.b]