Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
1.4 kB
4
Indexable
Never

import java.util.Scanner;

public class Solution {
	static String[] a = new String[305];
	static int[][] d = new int[305][305];
	static int[] dx = {-1, 1, 0, 0};
	static int[] dy = {0, 0, -1, 1};
	static int n, m;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for(int t=1; t<=T; t++) {
			n=sc.nextInt();
			m=sc.nextInt();
			int x=-1, y=-1;
			int xx=-1, yy=-1;
			for(int i=0; i<n; i++) {
				String s = sc.next();
				a[i] = s;
				for(int j=0; j<s.length(); j++) {
					if(s.charAt(j)=='Y') {
						x=i; y=j;
					}else if(s.charAt(j)=='T') {
						xx=i; yy=j;
					}
				}
			}
			for(int i=0; i<n; i++) {
				for(int j=0; j<m; j++) {
					d[i][j] = 100000007;
				}
			}
			BFS(x, y);
			System.out.println("Case #"+t);
			System.out.println(d[xx][yy]-1);
		}
	}
	
	static void BFS(int x, int y) {
		d[x][y] = 1;
		int[] qx = new int[305];
		int[] qy = new int[305];
		int l=0, r=0;
		qx[r]=x; qy[r++]=y;
		while(l<r) {
			x = qx[l]; y=qy[l++];
			for(int i=0; i<4; i++) {
				int xx = x+dx[i];
				int yy = y+dy[i];
//				System.out.println(a[xx].charAt(yy));
				if(xx>=0 && xx<n && yy>=0 && yy<m && a[xx].charAt(yy)!='S' && a[xx].charAt(yy)!='R') {
					int tmp = d[x][y]+1;
					if(a[xx].charAt(yy)=='B') {
						tmp = d[x][y]+2;
					}
					if(tmp<d[xx][yy]) {
						d[xx][yy]=tmp;
						qx[r] = xx; qy[r++]=yy;
					}
				}
			}
		}
	}
}