Untitled

mail@pastecode.io avatar
unknown
plain_text
7 months ago
2.8 kB
1
Indexable
Never
package practice;
import java.io.FileInputStream;
import java.util.Scanner;
class index{
	int row;
	int col;
	public index(int x, int y) {
		this.row = x;
		this.col = y;
	}
}
public class battle_city {
	static int N,M,rear,front,min,re,ce ;
	static index[] queue;
	static void push(index x) {
		rear++;
		queue[rear] =x;
	}
	static index pop() {
		front++;
		return queue[front-1];
		
	}
	static boolean isempty() {
		if(front == rear+1) {
			return true;
		}
		return false;
	}
 	static char[][] map;
	static int[][]visit;
	static int[] dichchuyenrow = {-1,0,1,0};
	static int[] dichchuyencol = {0,1,0,-1};
	public static void main(String[] args)  throws Exception{
		System.setIn(new FileInputStream("src/practice/input.txt"));
		Scanner scanner = new Scanner(System.in);
		int T = scanner.nextInt();
		for(int t =1;t<= T;t++) {
			System.out.println("Case #"+t);
			N = scanner.nextInt();
			M = scanner.nextInt();
			queue = new index[N*M+10000];
			rear =-1;
			front =0;
			map = new char[N][M];
			visit = new int[N][M];
			
			for(int i = 0;i<N;i++) {
				String string = scanner.next();
				for(int j =0;j<M;j++) {
					map[i][j] = string.charAt(j);
					if(map[i][j] == 'Y') {
						index stIndex = new index(i, j);
						push(stIndex);
						visit[i][j] = 1;
						
					}
					if(map[i][j] == 'T') {
						re = i;
						ce =j;
					}
				}
			}
			int ans = Integer.MAX_VALUE;
			while(!isempty()) {
				index curIndex = pop();
				for(int i =0;i<4;i++) {
					int nextr = curIndex.row+dichchuyenrow[i];
					int nextc = curIndex.col+dichchuyencol[i];
					if(nextr >=0 && nextr <N && nextc >= 0 && nextc <M ) {
						if(map[nextr][nextc] == 'B' && (visit[nextr][nextc] == 0|| 
								visit[curIndex.row][curIndex.col] +1 < visit[nextr][nextc]  )) {
							index newin = new index(nextr, nextc);
							visit[nextr][nextc] = visit[curIndex.row][curIndex.col]+2;
							push(newin);
						}
						
						if(map[nextr][nextc] == 'E' && (visit[nextr][nextc] == 0|| 
								visit[curIndex.row][curIndex.col] +1 < visit[nextr][nextc]  )) {
							index newin = new index(nextr, nextc);
							visit[nextr][nextc] = visit[curIndex.row][curIndex.col]+1;
							push(newin);
						}
						if(map[nextr][nextc] == 'T' && (visit[nextr][nextc] == 0|| 
								visit[curIndex.row][curIndex.col] +1 < visit[nextr][nextc]  )) {
							
							visit[nextr][nextc] = visit[curIndex.row][curIndex.col]+1;
							if(visit[nextr][nextc] < ans) {
								ans = visit[nextr][nextc];
							}
						}
						
					}
					
				}
			}
			if(ans == Integer.MAX_VALUE) {
				System.out.println("-1");
			}
			else
				System.out.println(ans-1);
			
			
			
			
			
		}
		
		
	}

}
Leave a Comment