/* 这题实在调糊了 借鉴的题解的一些判断方法 位运算大法好 - - 因为要集齐所有的宝石所以状态压缩一下 f[i][j][s]将s化为二进制 每一0表示该宝石没有 1表示该宝石有 有：到（i,j）这个点时 宝石收集状况为s的状态是否存在 */ #include<iostream> #include<cstdio> #include<cstring> #include<queue> using namespace std; int T,n,m,k,f[210][210][33],sx,sy,ex,ey,num; int xx[5]={0,0,0,1,-1}; int yy[5]={0,1,-1,0,0}; char s[210][210]; struct point { int mx, my, step, sum; point (int xx, int yy, int tt, int ss):mx(xx), my(yy), step(tt), sum(ss){}; }; struct door { int xi, yi; }door[15]; bool check(int s) { int cnt=0; for(int i=0;i<=4;i++) if((s>>i)&1==1) cnt++; return(cnt>=k); } int main() { scanf("%d",&T); while(T--) { memset(f,0,sizeof(f)); memset(s,0,sizeof(s)); num=0; queue<point> q; int falg=0; scanf("%d%d%d",&n,&m,&k); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { cin>>s[i][j]; if(s[i][j]=='S') { s[i][j]='.'; sx=i; sy=j; } if(s[i][j]=='E') { s[i][j]='.'; ex=i; ey=j; } if(s[i][j]=='$') { num++; door[num].xi=i; door[num].yi=j; } } q.push(point(sx,sy,0,0)); f[sx][sy][0]=1;//初始状态存在 while(!q.empty()) { point tmmp=q.front(); q.pop(); int nx=tmmp.mx; int ny=tmmp.my; int su=tmmp.sum; int time=tmmp.step; if(nx==ex&&ny==ey&&check(su))//判断是否符合条件了 { printf("%d\n",tmmp.step); falg=1;//多组数据害死人啊 一开始return 0 了 } if(falg)break; if(s[nx][ny]=='.')//一般的情况 直接周围的点入队 for(int i=1;i<=4;i++) { int ox=nx+xx[i]; int oy=ny+yy[i]; if(ox>0&&ox<=n&&oy>0&&oy<=m&&f[ox][oy][su]==0&&s[ox][oy]!='#') { f[ox][oy][su]=1; q.push(point(ox,oy,time+1,su)); } } if(s[nx][ny]=='$')//传送门 把所有传送门周围的点都入队 { for(int i=1;i<=num;i++) for(int j=1;j<=4;j++) { int ox=door[i].xi+xx[j]; int oy=door[i].yi+yy[j]; if(ox>0&&ox<=n&&oy>0&&oy<=m&&f[ox][oy][su]==0&&s[ox][oy]!='#') { f[ox][oy][su]=1; q.push(point(ox,oy,time+1,su)); } } } if(s[nx][ny]>='0'&&s[nx][ny]<='4')//开始收集宝石了 { int si=su|(1<< (s[nx][ny]-'0'));//转化出新状态 for(int i=1;i<=4;i++) { int ox=nx+xx[i]; int oy=ny+yy[i]; if(ox>0&&ox<=n&&oy>0&&oy<=m&&f[ox][oy][si]==0&&s[ox][oy]!='#') { f[ox][oy][si]=1; q.push(point(ox,oy,time+1,si)); } } } } if(!falg) printf("oop!\n"); } return 0; }