Untitled
plain_text
2 months ago
3.4 kB
2
Indexable
Never
package Battle_City; import java.io.FileInputStream; import java.io.FileNotFoundException; import java.util.Scanner; public class Solution { static int n, m, xstart, ystart, xend, yend, res; static int[][] visit, lan; static char[][] a; static int[] dx = { 0, 1, 0, -1 }, dy = { 1, 0, -1, 0 }, queueX = new int[9000005], queueY = new int[9000005]; public static void BFS() { int front = 0, rear = 0; queueX[front] = xstart; queueY[front] = ystart; lan[xstart][ystart] = 0; visit[xstart][ystart] = 1; while (front <= rear) { int x = queueX[front], y = queueY[front]; int c = lan[x][y]; visit[x][y] = 2; for (int i = 0; i < 4; i++) { int newx = x + dx[i], newy = y + dy[i]; if (newx >= 0 && newy >= 0 && newx < n && newy < m && a[newx][newy] != 'R' && a[newx][newy] != 'S') { if (a[newx][newy] == 'B') { if (visit[newx][newy] == 0) { rear++; queueX[rear] = newx; queueY[rear] = newy; visit[newx][newy] = 1; lan[newx][newy] = c + 2; }else if (visit[newx][newy] == 2 && c+2 <lan[newx][newy]) { rear++; queueX[rear] = newx; queueY[rear] = newy; visit[newx][newy] = 1; lan[newx][newy] = Math.min(c + 2, lan[newx][newy]); }else{ lan[newx][newy] = Math.min(c + 2, lan[newx][newy]); } } if (a[newx][newy] == 'E') { if (visit[newx][newy] == 0) { rear++; queueX[rear] = newx; queueY[rear] = newy; visit[newx][newy] = 1; lan[newx][newy] = c + 1; }else if (visit[newx][newy] == 2 && c+1 <lan[newx][newy]) { rear++; queueX[rear] = newx; queueY[rear] = newy; visit[newx][newy] = 1; lan[newx][newy] = Math.min(c + 1, lan[newx][newy]); } else { lan[newx][newy] = Math.min(c + 1, lan[newx][newy]); } } if (a[newx][newy] == 'T') { if (visit[newx][newy] == 0) { rear++; queueX[rear] = newx; queueY[rear] = newy; visit[newx][newy] = 1; lan[newx][newy] = c + 1; } else { lan[newx][newy] = Math.min(c + 1, lan[newx][newy]); } } } } front++; } } public static void main(String[] args) { try { System.setIn(new FileInputStream("input.txt")); } catch (FileNotFoundException e) { // TODO Auto-generated catch block e.printStackTrace(); } Scanner scanner = new Scanner(System.in); int test = scanner.nextInt(); for (int t = 1; t <= test; t++) { n = scanner.nextInt(); m = scanner.nextInt(); a = new char[n][m]; visit = new int[n][m]; lan = new int[n][m]; for (int i = 0; i < n; i++) { String s = scanner.next(); for (int j = 0; j < m; j++) { a[i][j] = s.charAt(j); if (a[i][j] == 'Y') { xstart = i; ystart = j; } if (a[i][j] == 'T') { xend = i; yend = j; } } } res = 0; BFS(); // for (int i = 0; i < n; i++) { // for (int j = 0; j < m; j++) { // System.out.print(lan[i][j] + " "); // } // System.out.println(); // } if (visit[xend][yend] == 0) { res = -1; } else { res = lan[xend][yend]; } System.out.println("Case #" + t + "\n" + res); } scanner.close(); } }