#include <iostream>#include <stdio.h>#include <string.h>#include <stack>#include <queue>#include <map>#include <set>#include <vector>#include <math.h>#include <algorithm>using namespace std;#define ls 2*i#define rs 2*i+1#define up(i,x,y) for(i=x;i<=y;i++)#define down(i,x,y) for(i=x;i>=y;i--)#define mem(a,x) memset(a,x,sizeof(a))#define w(a) while(a)#define LL long longconst double pi = acos(-1.0);#define Len 100005#define mod 1000000007const int inf = 1<<30;struct Point{ int x,y,di,t; Point() {} Point(int a,int b,int c,int d):x(a),y(b),di(c),t(d) {}};int n,m,p;int di[4][2]= {{0,-1},{0,1},{-1,0},{1,0}};int dis[15][15][5];char mat[15][15];int main(){ int t,i,j,k; scanf("%d",&t); w(t--) { scanf("%d%d%d",&n,&m,&p); int stx,sty,enx,eny; up(i,0,n-1) { scanf("%s",mat[i]); up(j,0,m-1) { if(mat[i][j]=='@') { stx=i; sty=j; } else if(mat[i][j]=='$') { enx=i; eny=j; } } } up(i,0,14) { up(j,0,14) { up(k,0,4) { dis[i][j][k] = inf-1; } } } dis[stx][sty][0]=0; queue<Point> q; q.push(Point(stx,sty,0,0)); while(!q.empty()) { Point ss=q.front(); q.pop(); Point ss2=ss; ss2.t++; if(ss2.t%p==0) { ss2.di=(ss2.di-1+4)%4; } int dd=ss2.di; if(dis[ss.x][ss.y][dd]>dis[ss.x][ss.y][ss.di]+1) { dis[ss.x][ss.y][dd]=dis[ss.x][ss.y][ss.di]+1; q.push(Point(ss.x,ss.y,dd,ss2.t)); } dd=(ss2.di-1+4)%4; if(dis[ss.x][ss.y][dd]>dis[ss.x][ss.y][ss.di]+1) { dis[ss.x][ss.y][dd]=dis[ss.x][ss.y][ss.di]+1; q.push(Point(ss.x,ss.y,dd,ss2.t)); } dd=(ss2.di+1)%4; if(dis[ss.x][ss.y][dd]>dis[ss.x][ss.y][ss.di]+1) { dis[ss.x][ss.y][dd]=dis[ss.x][ss.y][ss.di]+1; q.push(Point(ss.x,ss.y,dd,ss2.t)); } int x=ss.x+di[ss.di][0]; int y=ss.y+di[ss.di][1]; if(x>=0&&y>=0&&x<n&&y<m) if(mat[x][y]!='*') if(dis[x][y][ss2.di]>dis[ss.x][ss.y][ss.di]+1) { dis[x][y][ss2.di]=dis[ss.x][ss.y][ss.di]+1; q.push(Point(x,y,ss2.di,dis[x][y][ss2.di])); } } int ans=inf; for(int i=0; i<4; i++) ans=min(ans,dis[enx][eny][i]); if(ans==inf-1) printf("YouBadbadn"); else printf("%dn",ans); } return 0;}
