Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
2.0 kB
1
Indexable
Never
package day21_2706;

import java.util.Scanner;

public class crazy_kinng {
	
	static int row, col, sx, sy, ex, ey; 
	static int[][] map, visit;
	static int[][] dh = {{-1, -2}, {-2, -1}, {-2, 1}, {-1, 2}, {1, 2}, {2, 1}, {2, -1}, {1, -2}};
	static int[][] dk = {{-1, -1, -1, 0, 1, 1, 1, 0}, 
						 {-1, 0, 1, 1, 1, 0, -1, -1}};
	static int[] horsex, horsey;
	
	private static void BFS(){
		MyQueue qx = new MyQueue(row * col);
		MyQueue qy = new MyQueue(row * col);
		qx.enqueue(sx); qy.enqueue(sy);
		
		int x, y, dx, dy;
		while(!qx.isEmpty()){
			x = qx.dequeue(); y = qy.dequeue();
			for(int i = 0; i < 8; i++){
				dx = x + dk[0][i]; dy = y + dk[1][i];
				if(dx < row && dy < col && dx >= 0 && dy >= 0 && visit[dx][dy] == 0){
					visit[dx][dy] = visit[x][y] + 1;
					qx.enqueue(dx); qy.enqueue(dy);
					if(dx == ex && dy == ey) return;
				}
			}
		}
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub

		Scanner sc = new Scanner(System.in);
		int testcase = sc.nextInt();
		for(int tc = 1; tc <= testcase; tc++){
			col = sc.nextInt(); row = sc.nextInt();
			
			map = new int[row][col]; visit = new int[row][col];
			horsex = new int[row * col]; horsey = new int[row * col];
			
			sc.nextLine();
			int dx, dy;
			for(int i = 0; i < row; i++){
				String line = sc.nextLine();
				for(int j = 0; j < col; j++){
					char c = line.charAt(j);
					if(c == 'Z'){
//						map[i][j] = 1;
						visit[i][j] = -1;
						for(int k = 0; k < 8; k++){
							dx = i + dh[k][0]; dy = j + dh[k][1];
							if(dx >= 0 && dy >= 0 && dx < row && dy < col && visit[dx][dy] != -1){
								visit[dx][dy] = -1;
							}
						}
//						jump(i, j);
					}
					else if(c == 'A'){
						sx = i; sy = j;
					}
					else if(c == 'B'){
						ex = i; ey = j;
					}
				}
			}
			visit[sx][sy] = 0;
			visit[ex][ey] = 0;
			BFS();
			
			if(visit[ex][ey] == 0) System.out.println(-1);
			else System.out.println(visit[ex][ey]);
			
			
		}
	}
}