Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
3.2 kB
16
Indexable
Never
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class BattleCity {
	static int dx[] = { 0, 0, 1, -1 };
	static int dy[] = { 1, -1, 0, 0 };
	static int Qx[];
	static int Qy[];
	static int visit[][];
	static char a[][];
	static int m, n;
	static int d[][];
	static int xY, yY, xT, yT;

	public static void main(String[] args) {
		try {
			System.setIn(new FileInputStream("battleCity"));
		} catch (FileNotFoundException e) {
			e.printStackTrace();
		}
		Scanner sc = new Scanner(System.in);
		int numTest = sc.nextInt();
		for (int tc = 1; tc <= numTest; tc++) {

			m = sc.nextInt();
			n = sc.nextInt();
			sc.nextLine();
			a = new char[m][n];
			for (int i = 0; i < m; i++) {
				String line = sc.nextLine();
				for (int j = 0; j < n; j++) {
					a[i][j] = line.charAt(j);
					if (a[i][j] == 'Y') {
						xY = i;
						yY = j;

					}
					if (a[i][j] == 'T') {
						xT = i;
						yT = j;

					}
				}
			}
			Qx = new int[100000000];
			Qy = new int[100000000];
			//visit = new int[m + 2][n + 2];
			d = new int[m][n];
			for (int i = 0; i < m; i++) {
				for (int j = 0; j < n; j++) {
					d[i][j] = -1;
				}
			}
			System.out.println("Case #" + tc);
			BFS(xY, yY);
			if (d[xT][yT] == -1)
				System.out.println("-1");
			else
				System.out.println(d[xT][yT]);
			
//			for (int i = 0; i < m; i++) {
//				for (int j = 0; j < n; j++) {
//					System.out.print(d[i][j]+ " ");
//				}
//				System.out.println();
//			}
		}
	}

	public static int mrank(int x, int y) {
		if (a[x][y] == 'B') return 2;
		if (a[x][y] == 'Y' || a[x][y] == 'E' || a[x][y] == 'T') return 1;
		return 0;
	}
	
	public static void BFS(int x, int y) {
		int front = 0;
		int rear = 0;

		Qx[rear] = x;
		Qy[rear] = y;
		rear++;
		d[x][y] = 0;
		while (front != rear) {
			int tmpx = Qx[front];
			int tmpy = Qy[front];
			front++;

			for (int i = 0; i < 4; i++) {
				int xx = tmpx + dx[i];
				int yy = tmpy + dy[i];

				if (xx >= 0 && xx < m && yy >= 0 && yy < n) {
					if (a[xx][yy] == 'E' || a[xx][yy] == 'B' || a[xx][yy] == 'T') {
						if (d[xx][yy] == -1) {
							d[xx][yy] = d[tmpx][tmpy] + mrank(xx, yy);
							Qx[rear] = xx;
							Qy[rear] = yy;
							rear++;
						} else {

//							if (a[xx][yy] == 'E' || a[xx][yy] == 'T'
//									&& d[xx][yy] > (d[tmpx][tmpy] + 1)) {
//								d[xx][yy] = d[tmpx][tmpy] + 1;
//								visit[xx][yy] = 1;
//								Qx[rear] = xx;
//								Qy[rear] = yy;
//								rear++;
//							} else if (a[xx][yy] == 'B'
//									&& d[tmpx][tmpy] + 2 < d[xx][yy]) {
//								d[xx][yy] = d[tmpx][tmpy] + 2;
//								Qx[rear] = xx;
//								Qy[rear] = yy;
//								rear++;
//							}
							if (d[xx][yy] > d[tmpx][tmpy] + mrank(xx, yy)) {
								d[xx][yy] = d[tmpx][tmpy] + mrank(xx, yy);
								//visit[xx][yy] = 1;
								Qx[rear] = xx;
								Qy[rear] = yy;
								rear++;
							}
						}
					}
				}
			}

		}

		// for (int i = 0; i < m; i++) {
		// for (int j = 0; j < n; j++) {
		// System.out.print(d[i][j] + " ");
		//
		// }
		// System.out.println();
		// }
		// System.out.println();

	}
}