题解：
练代码功底的题目
首先思路嘛很显然 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 <bits/stdc++.h> using namespace std; #define maxn1 16390 #define maxn2 15 int 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<re> 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<len;i++) { int tmp=now-((now>>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<len;j++) { now>>=2; cnt+=2; } re x3={((tmp.c-(now<<cnt))<<2)+js(x+dx[i],y+dy[i],x,y),tmp.d}; return(x3); } char c[100]; #define INF 1e9 int 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<<k)-1; memset(ff,1,sizeof(ff)); int ans=INF,xans,yans,zans,eans=goal; while (!q.empty()) { re x=q.front(); q.pop(); if (dp[x.a][x.b][x.c][x.d]>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<dp[x.a+dx[i]][x.b+dy[i]][r.a][r.b]||dp[x.a+dx[i]][x.b+dy[i]][r.a][r.b]==-1) { pre2[1][x.a+dx[i]][x.b+dy[i]][r.a][r.b]=(i-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]<ans) { ans=dp[x.a+dx[i]][x.b+dy[i]][r.a][r.b]; xans=x.a+dx[i]; yans=x.b+dy[i]; zans=r.a; } } } ff[x.a][x.b][x.c][x.d]=1; } int cnt=0; if (ans==INF) cout<<"No solution."; else { cout<<ans<<endl; while (pre[xans][yans][zans][eans]!=-1) { int x=pre2[1][xans][yans][zans][eans]*2+pre2[2][xans][yans][zans][eans]; jl[++cnt]=x; zans=pre[xans][yans][zans][eans]; if (ft[xans][yans]) eans^=1<<(ft[xans][yans]-1); if (x==0) xans--; if (x==1) xans++; if (x==2) yans--; if (x==3) yans++; } for (int i=cnt;i;i--) { if (jl[i]==0) cout<<'D'; if (jl[i]==1) cout<<'U'; if (jl[i]==2) cout<<'R'; if (jl[i]==3) cout<<'L'; } } return 0; }