# Untitled

unknown
plain_text
a year ago
2.7 kB
6
Indexable
Never
```import java.util.Scanner;

public class Solution {

static Scanner scanner=new Scanner(System.in);

static class Node{
int x,y,cost;
Node(int x,int y,int cost){
this.x=x;
this.y=y;
this.cost=cost;
}
}

static class Queue{
Node front;
int n;
void push(Node node){
Node tmp=front;
++n;

if(front==null)
front=node;
else if(node.cost<front.cost){
front=node;
}
else{
}
}
void pop(){
if(front==null)
return;
--n;
}
}

static void exec(int test){
int n=Integer.parseInt(scanner.next()),m=Integer.parseInt(scanner.next());
/*m,n: me cung m hang, n cot
* ko the di qua cac con song hay tuong, nhung co the pha huy tuong gach
* bang cach ban no
* buc tuong gach tro thanh rong neu ban gap no
* tuong thep thi ko the hit
* moi lan chi dc di chuyen 4 huong
* hoac ban vao 1 trong 4 huong
* ma ko di chuyen
* viec ban se di thang
* can it nhat bao nhieu luot de den dc target
* o moi vi tri thi dc di chuyen hoac ban vao 1 trong 4 cai ma ko di chuyeb
* */
char[][] a=new char[n][m];
int[][] cost=new int[n][m];
int sx=-1,sy=-1,ex=-1,ey=-1;

for(int i=0;i<n;++i){
char[] tmp=scanner.next().toCharArray();
for(int j=0;j<m;++j){
a[i][j]=tmp[j];
if(tmp[j]=='Y'){
sx=i;sy=j;
}else if(tmp[j]=='T'){
ex=i;ey=j;
}
}
}

for(int i=0;i<n;++i) for(int j=0;j<m;++j)
cost[i][j]=Integer.MAX_VALUE;
cost[sx][sy]=0;

int[][] dir={{0,-1},{0,1},{-1,0},{1,0}};
Queue queue=new Queue();
queue.push(new Node(sx,sy,0));
while(queue.n>0){
int x=queue.front.x,y=queue.front.y,cost1=queue.front.cost;
queue.pop();

if(cost1>cost[x][y]) continue;

for(int i=0;i<4;++i){
int nx=x+dir[i][0],ny=y+dir[i][1];
if(nx>=0 && nx<n && ny>=0 && ny<m && a[nx][ny]!='S' && a[nx][ny]!='R'){
if(a[nx][ny]=='B' && cost[nx][ny]>cost[x][y]+2){
cost[nx][ny]=cost[x][y]+2;
queue.push(new Node(nx,ny,cost[nx][ny]));
}
else if((a[nx][ny]=='E' || a[nx][ny]=='T') && cost[nx][ny]>cost[x][y]+1){
cost[nx][ny]=cost[x][y]+1;
queue.push(new Node(nx,ny,cost[nx][ny]));
}
}
}
}

System.out.printf("Case #%d\n%d\n",test,cost[ex][ey]==Integer.MAX_VALUE?-1:cost[ex][ey]);
}

public static void main(String[] args) {

int t=Integer.parseInt(scanner.next());

for(int test=1;test<=t;++test)
exec(test);

scanner.close();
}
}
```