#include #include #include #include #include #include #include #include #include using namespace std; const int maxn = 115; const int inf = 9999999; char mat[ maxn ][ maxn ]; int vis[ maxn ][ maxn ][ 2 ][ 2 ]; const int dx[]={1,-1,0,0}; const int dy[]={0,0,1,-1}; struct Pos{ int x,y; }; struct Node{ int x,y,ti; int D,E;//flag }; Pos D,S,E; void init(){ for( int i=0;i=0&&p.x=0&&p.y q; while( !q.empty() ) q.pop(); q.push( cur ); int ans = inf; vis[ cur.x ][ cur.y ][ cur.D ][ cur.E ] = 1; while( !q.empty() ){ cur = q.front(); q.pop(); if( cur.ti>aim_ti ) continue; //printf("cur:x=%d,y=%d,ti=%d\n",cur.x,cur.y,cur.ti); if( cur.x==D.x&&Judge1( cur )==true ) cur.D = 1; if( cur.x==E.x&&Judge2( cur )==true ) cur.E = 1; if( cur.y==D.y&&Judge3( cur )==true ) cur.D = 1; if( cur.y==E.y&&Judge4( cur )==true ) cur.E = 1; if( cur.D==1 ) { if( cur.E==1 ){ if( ans>cur.ti ){ ans = cur.ti; } } } //printf("ans:%d\n",ans); for( int i=0;i<4;i++ ){ nxt = cur; nxt.x+=dx[i]; nxt.y+=dy[i]; nxt.ti++; if( in( nxt,n,m )==true&&mat[nxt.x][nxt.y]!='X'&&vis[nxt.x][nxt.y][nxt.D][nxt.E]==0 ){ vis[nxt.x][nxt.y][nxt.D][nxt.E] = 1; q.push(nxt); } } } if( ans>aim_ti ) return -1; else return ans; } int main(){ int ca,T; scanf("%d",&ca); T = 1; while( ca-- ){ int n,m,aim_ti; printf("Case %d:\n",T++); init(); scanf("%d%d%d",&n,&m,&aim_ti); for( int i=0;i